[C++] 백준 1238번: 파티 (다익스트라)

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

---

문제 이해하기

 문제의 요구사항은 다음과 같습니다.

N명의 학생이 최단거리로 X로 이동하고 다시 집으로 돌아올 때, 왕복 시간이 가장 오래 걸리는 학생의 왕복 시간을 구하여라.

---

시간복잡도 어림하기

플로이드 워셜 알고리즘

 최단 경로 중 가장 긴 경로를 구하는 문제이므로 각 학생별로 왕복 최단거리를 구해야합니다. 이번 문제는 각 지점에서 다른 지점까지의 최단 경로 정보가 필요하므로 플로이드 워셜 알고리즘을 사용할 수 있습니다.

 플로이드 워셜 알고리즘은 O(N^3)의 시간복잡도를 가지는 알고리즘입니다. 이때, N의 최댓값이 1000이므로 N^3 = 1,000,000,000 (10억)입니다. 이는 제한 시간 내에 해결하기 어려운 수치이므로 다른 알고리즘을 사용해야합니다.

 

다익스트라 알고리즘

 또 다른 최단 경로 알고리즘으로 다익스트라 알고리즘이 있습니다. 다익스트라 알고리즘은 한 노드에서 다른 모든 노드까지의 최단거리를 구하는 알고리즘입니다. 이번 문제에서는 각 노드 별로 X에 도달하는 최단 경로가 필요하고 X에서 각 노드로 이동하는 최단거리가 필요합니다.

 X에서 각 노드로 이동하는 최단거리는 X를 시작으로 다익스트라 알고리즘을 한 번만 사용하여 구할 수 있습니다. 하지만, 각 노드에서 X로 이동하는 최단거리는 다익스트라 알고리즘을 N번 실행해야합니다.

 

 다익스트라 알고리즘의 시간복잡도는 O(ElogE)이고 문제에서 E의 최댓값은 10,000입니다. 이를 N + 1번 반복해야하므로 전체 시간복잡도는 1001 x 10000 log 10000 라고 할 수 있습니다. 이는 제한 시간에 해결하기 어려운 수치이므로 다른 아이디어를 사용해야합니다.

---

알고리즘 설계하기

 이전 단계에서는 두 최단 거리 알고리즘 모두 사용하기 어렵다는 결론을 얻을 수 있었습니다. 하지만, 기본 시간복잡도가 O(N^3)인 플로이드 워셜 알고리즘과 달리 O(ElogE)의 시간복잡도를 가지는 다익스트라 알고리즘은 연산 횟수만 줄일 수 있다면 제한 시간 내에 충분히 해결할 수 있는 알고리즘입니다.

 

 그렇다면 어떻게 시간복잡도를 줄일 수 있을까요? 힌트는 문제의 목적지가 하나라는 점에 있습니다.

 

 이번 문제는 모든 노드가 X로 향하고 X에서 각 노드로 이동하는 최단 경로 중 가장 긴 것을 구하는 문제입니다. 이때, 제한 시간 내로 문제를 해결하기 위해서는 다익스트라 알고리즘을 실행하는 시작 노드가 하나여야 합니다.

 X에서 다시 원래 노드로 돌아오는 것은 시작지점이 X로 하나지만, 각 노드에서 X에 이동하는 것은 시작 지점이 여러 개 입니다. 우리는 이를 하나의 시작점으로도 구할 수 있도록 변형해야합니다.

 

 여러 시작점을 하나로 바꾸는 것은 생각보다 단순한 전략입니다. 모든 노드가 동일한 목적지에 도달하므로 처음 입력을 받을 때, 그래프 방향을 반대로 저장하여 해결할 수 있습니다.

예를 들어,
A -> B로 이동하는데 3의 비용이 들고, B -> X로 이동하는 데 5의 비용이 들고, C -> B로 이동하는데 1의 비용이 든다고 해봅시다.
이를 반대로 뒤집어 저장한다면
B -> A의 비용이 3, X -> B의 비용이 5, B -> C의 비용이 1 입니다.

이를 그래프로 표현하면
X -- B -- A
       |
       -  C
와 같이 저장될 것입니다.

따라서 시작점이 여럿인 그래프를 시작점이 하나인 그래프로 변경할 수 있습니다.

 

 문제 해결 로직은 다음과 같습니다.

1. 입력을 받으면서 정방향 그래프, 역방향 그래프 두 개를 만든다.
 - 정방향 그래프는 X에서 돌아오는 최단거리,
 - 역방향 그래프는 X로 향하응 최단거리를 구하기 위해 사용된다.
2. 각 그래프에서 X를 시작 노드로 하여 다익스트라 알고리즘을 실행한다.
3. X로 향하는 최단거리와 X에서 돌아오는 최단거리의 합이 가장 큰 것을 구한다.

 

---

알고리즘 구현하기

 최종 코드는 다음과 같습니다.

#include<iostream>
#include<queue>
#include<vector>
#define INF 1e9
using namespace std;

int n, m, x, dist1[1004], dist2[1004], ret = 0;
vector<pair<int, int>> adj1[1004], adj2[1004];
void dijkstra(int dist[1004], vector<pair<int, int>> adj[1004]){
    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
    dist[x] = 0;
    pq.push({0, x}); //시작 노드는 X
    int cur, d;
    while(!pq.empty()){
        cur = pq.top().second; //현재 노드
        d = pq.top().first; //시작점에서 현재 노드까지의 최단거리
        pq.pop();
        if(dist[cur] != d) continue; //더 이상 탐색할 필요 없는 경우

        for(auto next : adj[cur]){
            int temp = dist[cur] + next.second; //갱신할 최단거리
            if(dist[next.first] > temp){
                dist[next.first] = temp;
                pq.push({temp, next.first});
            }
        }
    }
}

int main(){
    /*입출력 성능 향상*/
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    cin >> n >> m >> x;
    int from, to, weight;
    for(int i = 0; i < m; i++){
        cin >> from >> to >> weight;
        adj1[from].push_back({to, weight}); //정방향 그래프
        adj2[to].push_back({from, weight}); //역방향 그래프
    }
    
    /*최단거리 배열 초기화*/
    fill(dist1, dist1 + 1004, INF);
    fill(dist2, dist2 + 1004, INF);

    /*다익스트라 알고리즘 실행*/
    dijkstra(dist1, adj1);
    dijkstra(dist2, adj2);
    
    /*가장 긴 최단거리 찾기*/
    for(int i = 1; i <= n; i++){
        if(i != x) ret = max(ret, dist1[i] + dist2[i]);
    }
    cout << ret;
    return 0;
}

 다른 그래프와 최단거리 배열에서 두 번 다익스트라 알고리즘을 실행해야하므로 이들을 파라미터로 받는 dijkstra 함수를 정의했습니다. 다익스트라 알고리즘에서 사용하는 priority queue는 매 시행마다 초기화된 것으로 사용해야하므로 지역변수로 선언했습니다.

---