[백준/C++] 13911번: 집 구하기

문제 & 링크

https://www.acmicpc.net/problem/13911

 

풀이

1. 음의 가중치가 없는 그래프에서 최단 거리를 구해야 하기에 다익스트라 알고리즘을 사용한다.

2. x세권인지 아닌지 판단하는 값이 주어지기에, 다익스트라 알고리즘에서 우선순위 큐에 넣을 때 이 값을 고려한다.

3. 모든 집에서 다익스트라를 수행 할 경우 x세권이 아님에도 탐색 대상이 되는 경우가 있기에 비효율적이다.

4. 맥도날드 or 스타벅스에서 다익스트라를 수행하여 x세권인 집만 탐색을 한다.

5. 모든 맥도날드 or 스타벅스에서 다익스트라를 한 번씩 수행하면, 최악의 경우 9,999개의 노드에 대한 다익스트라 수행으로 시간 초과가 나게 된다. 

6. 가상 노드라는 개념을 추가하여 모든 맥도날드의 시작점을 하나로 묶고, 모든 스타벅스의 시작점을 하나로 묶는다. 이때 가중치를 0으로 설정하여 가상 노드가 곧 각각의 맥도날드 or 스타벅스를 의미하게 된다. 즉 맥도날드 + 스타벅스의 개수만큼 수행해야 했던 다익스트라를 2번의 다익스트라로 줄일 수 있다.

7. 맥도날드 가상 노드에 대한 다익스트라 결과와 스타벅스 가상 노드에 대한 다익스트라 결과를 합쳐 정답을 구한다.

 

코드

#include <iostream>
#include <queue>
#include <vector>
#include <algorithm>

using namespace std;

int INF = 987654321;
int V, E;
vector<pair<int, int>> adj[10003];
int dist[10003][2]; // 맥도날드에 대한 dist, 스타벅스에 대한 dist
bool is_MS[10003]; // 맥도날드 or 스타벅스인지

// s는 시작 노드, d는 x세권인지 아닌지 판단을 위한 거리, kind는 맥도날드 or 스타벅스
void dijkstra(int s, int d, int kind) { 
    for (int i = 1; i <= V; i++) {
        dist[i][kind] = INF;
    }

    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;

    pq.push({ 0, s });
    dist[s][kind] = 0;

    while (!pq.empty()) {
        int x = pq.top().second;
        int cost = pq.top().first;
        pq.pop();

        for (int i = 0; i < adj[x].size(); i++) {
            int nx = adj[x][i].first;
            int ncost = cost + adj[x][i].second;

            if (ncost <= d && dist[nx][kind] > ncost) {
                pq.push({ ncost, nx });
                dist[nx][kind] = ncost;
            }
        }
    }
}

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

    cin >> V >> E;

    int u, v, w;
    for (int i = 0; i < E; i++) {
        cin >> u >> v >> w;

        adj[u].push_back({ v, w });
        adj[v].push_back({ u, w });
    }

    int M, x, S, y;
    int num;

    cin >> M >> x;
    
    for (int i = 0; i < M; i++) {
        cin >> num;
        is_MS[num] = true;

        // 가상 노드를 생성, 10001번 노드는 모든 맥도날드 노드와 거리 0으로 연결
        adj[10001].push_back({ num, 0 }); 
    }
    dijkstra(10001, x, 0);

    cin >> S >> y;
    for (int i = 0; i < S; i++) {
        cin >> num;
        is_MS[num] = true;

        // 가상 노드를 생성, 10002번 노드는 모든 스타벅스 노드와 거리 0으로 연결
        adj[10002].push_back({ num, 0 }); 
    }
    dijkstra(10002, y, 1);

    int ans = INF;
    for (int i = 1; i <= V; i++) {
        if (!is_MS[i]) {
            ans = min(ans, dist[i][0] + dist[i][1]);
        }
    }

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