백준 1238 - 파티 (골드3) 풀이

문제 요약

N명의 학생이 각자 집에서 X 마을로 갔다가 돌아온다. 각 학생의 왕복 거리 중 최댓값을 구하는 문제.

• 단방향 그래프, 가중치 있음
• N ≤ 1000, M ≤ 10000

---

접근 방식

필요한 정보

모든 학생 i에 대해 두 가지 거리가 필요하다.

• i → X 거리
• X → i 거리

X → i는 X를 시작점으로 다익스트라 1번이면 전부 구해진다.
문제는 i → X인데, 시작점이 N개라 단순하게 하면 N번 다익스트라를 돌려야 한다.

역방향 그래프 아이디어

i → X의 최단경로를 뒤집으면 X → i (역방향 그래프)의 최단경로와 동일하다.

예시: A → B → C → X 라는 경로가 있으면,
간선을 전부 뒤집은 그래프에서 X → C → B → A 가 같은 비용으로 존재한다.

따라서 역방향 그래프를 만들어서 X를 시작점으로 다익스트라를 돌리면,
i → X 거리를 한 번에 전부 구할 수 있다.

결과적으로 다익스트라를 2번만 돌리면 된다.

| 그래프 | 시작점 | 구하는 것 | |---|---|---| | 정방향 adj | X | X → i 거리 | | 역방향 radj | X | i → X 거리 |

---

구현 포인트

입력을 받을 때 정방향과 역방향을 동시에 저장한다.

u → v, 가중치 w 입력 시:
  adj[u]  에 {w, v} 추가  (정방향)
  radj[v] 에 {w, u} 추가  (역방향)

---

최종 코드

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

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    const int INF = 1e9;

    int N, M, X;
    cin >> N >> M >> X;

    vector<vector<pair<int, int>>> adj(N+1);
    vector<vector<pair<int, int>>> radj(N+1);

    for(int i = 0; i < M; i++){
        int u, v, w;
        cin >> u >> v >> w;
        adj[u].push_back({w, v});
        radj[v].push_back({w, u});
    }

    // X → i 거리 (정방향)
    vector<int> distance(N+1, INF);
    distance[X] = 0;
    priority_queue<pair<int,int>, vector<pair<int,int>>, greater<pair<int,int>>> pq;
    pq.push({0, X});
    while(!pq.empty()){
        auto [d, node] = pq.top(); pq.pop();
        if(d > distance[node]) continue;
        for(const auto &next : adj[node]){
            auto [nw, nv] = next;
            int temp = distance[node] + nw;
            if(temp < distance[nv]){
                distance[nv] = temp;
                pq.push({distance[nv], nv});
            }
        }
    }

    // i → X 거리 (역방향 그래프에서 X 출발)
    vector<int> rdistance(N+1, INF);
    rdistance[X] = 0;
    priority_queue<pair<int,int>, vector<pair<int,int>>, greater<pair<int,int>>> pq2;
    pq2.push({0, X});
    while(!pq2.empty()){
        auto [d, node] = pq2.top(); pq2.pop();
        if(d > rdistance[node]) continue;
        for(const auto &next : radj[node]){
            auto [nw, nv] = next;
            int temp = rdistance[node] + nw;
            if(temp < rdistance[nv]){
                rdistance[nv] = temp;
                pq2.push({rdistance[nv], nv});
            }
        }
    }

    int result = 0;
    for(int i = 1; i <= N; i++){
        result = max(result, distance[i] + rdistance[i]);
    }
    cout << result;

    return 0;
}

---

복잡도

| | N × 다익스트라 | 역방향 그래프 | |---|---|---| | 시간복잡도 | O(N × (N+M) log N) | O((N+M) log N) | | 다익스트라 횟수 | N번 | 2번 |

---

배운 점

역방향 그래프는 "모든 노드 → 특정 노드" 거리를 한 번에 구해야 할 때 강력한 도구다.
입력 시 radj[v].push_back({w, u}) 한 줄만 추가하면 구현도 간단하다.

위상정렬, SCC 등 다른 그래프 문제에서도 역방향 그래프가 핵심으로 등장하니 기억해두자.