[백준] 13911 집 구하기 (C++)

문제

원문 링크 : https://www.acmicpc.net/problem/13911

안양에 사는 상혁이는 4년간의 통학에 지쳐 서울에 집을 구하려고 한다. 상혁이가 원하는 집은 세가지 조건이 있다.

• 맥세권 : 맥세권인 집은 맥도날드와 집 사이의 최단거리가 x이하인 집이다.
• 스세권 : 스세권인 집은 스타벅스와 집 사이의 최단거리가 y이하인 집이다.
• 맥세권과 스세권을 만족하는 집 중 최단거리의 합이 최소인 집

통학 때문에 스트레스를 많이 받은 상혁이는 집을 선택하는 데 어려움을 겪고 있다. 똑똑한 여러분이 상혁이 대신 이 문제를 해결해 주자. 이사 갈 지역의 지도가 그래프로 주어지고 맥도날드와 스타벅스의 위치가 정점 번호로 주어질 때 상혁이가 원하는 집의 최단거리의 합을 출력하는 프로그램을 작성하시오. (맥도날드와 스타벅스가 아닌 정점에는 모두 집이 있다.)

위의 예제 지도에서 사각형은 맥도날드를, 별은 스타벅스가 위치한 정점을 나타낸다. 각 원은 집이 있는 정점을 낸다. x가 6이고 y가 4일 때 가능한 집의 정점은 6이다. 맥도날드까지의 최단거리가 2, 스타벅스까지의 최단거리가 4로 총 합이 6이 되기 때문이다. 정점 7은 맥세권이면서 스세권이지만 맥도날드까지의 최단거리가 6, 스타벅스까지의 최단거리가 2로 총 합이 8로써 정점 6의 값보다 크므로 답이 아니다. 그 외의 정점 2, 3, 4는 맥세권이면서 스세권인 조건을 충족하지 못하므로 답이 될 수 없다.

풀이 및 구현

일반적인 다익스트라 알고리즘은 시작 정점을 하나로 설정하고 해당 정점에서 다른 정점들까지의 최단거리를 구한다.

이를 변형해서 시작 정점을 여러 개로 설정해서 다익스트라 알고리즘을 돌리면 시작 정점 쌍에서 다른 정점들까지의 최단거리를 구할 수 있다.

즉 맥도날드 정점들을 시작정점으로 한 번, 스타벅스 정점들을 시작정점으로 한 번 다익스트라 알고리즘을 돌리면 각 집에서 가장 가까운 맥도날드와 스타벅스를 구할 수 있다.

int M, x, S, y;
cin >> M >> x;
vector<int> m(V); // 맥도날드 정점
for (int i = 0; i < M; i++) {
    int a; cin >> a; m[a - 1] = 1;
}
cin >> S >> y;
vector<int> s(V); // 스타벅스 정점
for (int i = 0; i < S; i++) {
    int a; cin >> a; s[a - 1] = 1;
}

이를 위해 맥도날드나 스타벅스 정점의 경우 해당 배열의 값을 1로 설정해주고 다익스트라 함수의 인자로 넘겨주었다.

vector<ll> Dijkstra(vector<int>& v) {
    priority_queue<pair<ll, int>> pq;
    vector<ll> dist(V, INF);
    
    // 시작 정점을 모두 우선순위 큐에 넣어준다.
    for (int i = 0; i < V; i++) 
        if (v[i]) 
            pq.emplace(0, i), dist[i] = 0;

    while (!pq.empty()) {
        auto [cur_dist, cur_node] = pq.top(); pq.pop();
        cur_dist = -cur_dist;

        if (dist[cur_node] != cur_dist) continue;

        for (auto& [nxt_node, d] : adj[cur_node]) {
            ll nxt_dist = cur_dist + d;
            if (nxt_dist < dist[nxt_node]) {
                dist[nxt_node] = nxt_dist;
                pq.emplace(-nxt_dist, nxt_node);
            }
        }
    }
    return dist;
}

이후 다익스트라 함수에서 전달받은 배열 중 1인 정점들은 모두 시작정점으로 하여 다익스트라를 돌린 뒤 거리 배열을 반환해주면 각 집에서 맥도날드와 스타벅스까지의 거리를 각각 구할 수 있다.

ll mn = INF;
for (int i = 0; i < V; i++) 
    if (!m[i] && !s[i] && md[i] <= x && sd[i] <= y) 
        mn = min(mn, md[i] + sd[i]);

이후 맥도날드, 스타벅스가 아니면서 맥세권과 스세권인 집이면 최솟값을 갱신해 주었다.

이후 mn의 값이 INF 이면 -1을, 아니면 mn을 출력하면 된다.

코드

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
constexpr ll INF = LLONG_MAX;

int V;
vector<vector<pair<int, ll>>> adj;

vector<ll> Dijkstra(vector<int>& v) {
    priority_queue<pair<ll, int>> pq;
    vector<ll> dist(V, INF);

    for (int i = 0; i < V; i++) if (v[i]) pq.emplace(0, i), dist[i] = 0;

    while (!pq.empty()) {
        auto [cur_dist, cur_node] = pq.top(); pq.pop();
        cur_dist = -cur_dist;

        if (dist[cur_node] != cur_dist) continue;

        for (auto& [nxt_node, d] : adj[cur_node]) {
            ll nxt_dist = cur_dist + d;
            if (nxt_dist < dist[nxt_node]) {
                dist[nxt_node] = nxt_dist;
                pq.emplace(-nxt_dist, nxt_node);
            }
        }
    }
    return dist;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    int E; cin >> V >> E;
    adj.assign(V, vector<pair<int, ll>>());
    for (int i = 0; i < E; i++) {
        int s, e; ll w;
        cin >> s >> e >> w;
        adj[s - 1].emplace_back(e - 1, w);
        adj[e - 1].emplace_back(s - 1, w);
    }

    int M, x, S, y;
    cin >> M >> x;
    vector<int> m(V);
    for (int i = 0; i < M; i++) {
        int a; cin >> a; m[a - 1] = 1;
    }
    cin >> S >> y;
    vector<int> s(V);
    for (int i = 0; i < S; i++) {
        int a; cin >> a; s[a - 1] = 1;
    }
    vector<ll> md = Dijkstra(m), sd = Dijkstra(s);

    ll mn = INF;
    for (int i = 0; i < V; i++) if (!m[i] && !s[i] && md[i] <= x && sd[i] <= y) mn = min(mn, md[i] + sd[i]);

    if (mn == INF) cout << -1;
    else cout << mn;
}

후기

시작 정점이 여러 개로 설정하고 다익스트라를 하는 아이디어가 참신한 문제였다.