백준_파티

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

[ 나의 해결법 ]

이 문제는 다익스트라 알고리즘을 이용해서 풀면 된다. 그런데 그냥 다익스트라 알고리즘으로 풀면 시간초과가 난다. 시간복잡도를 계산하면 10억이 훌쩍 넘는다. 3중 for문을 돌기 때문이다.

다른 사람들의 질문들을 보니 플로이드 와샬 알고리즘을 이용한 사람도 있다. 그런데 나는 우선순위 큐를 이용한 알고리즘을 사용할 것이다. 코드는 아래와 같다.

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73

#include <iostream> #include <vector> #include <queue>   #define MAX_NODE    1000 #define INFINITE    1000000   using namespace std;   int N, M, X; int MinTime[MAX_NODE + 1], dist[MAX_NODE + 1]; vector<pair<int, int>> adj[MAX_NODE + 1];   void input() {     cin >> N >> M >> X;     for (int i = 0; i < M; i++) {         int from, to, time;         cin >> from >> to >> time;         adj[from].push_back(make_pair(to, time));     } }   int dikstra(int from, int to) {     priority_queue<pair<int, int>> pq;       for (int i = 1; i <= N; i++)         dist[i] = INFINITE;       dist[from] = 0;     pq.push(make_pair(0, from));           while (!pq.empty())     {         int min_dist = -pq.top().first;         int min_node = pq.top().second;         pq.pop();           for (int v = 0; v < adj[min_node].size(); v++) {             int next_node = adj[min_node][v].first;             int next_dist = min_dist + adj[min_node][v].second;             if (next_dist < dist[next_node]) {                 dist[next_node] = next_dist;                 pq.push(make_pair(-next_dist, next_node));             }         }     }     return dist[to]; }   int main() {     int MaxTime = 0;       input();       for (int v = 1; v <= N; v++)     {         if (v == X) continue;         MinTime[v] = dikstra(v, X);     }     dikstra(X, 1);       for (int v = 1; v <= N; v++)     {         MinTime[v] += dist[v];         if (MaxTime < MinTime[v])             MaxTime = MinTime[v];     }     cout << MaxTime;     return 0; }

전에 기본 다익스트라 알고리즘과 비교하면서 보자. 큰틀은 같다. 

1. 배열 dist에서 최소 거리를 찾기위해서, 우선순위 큐를 사용했다.

2. 찾은 최소거리에 연결된 노드를 방문하는데, vector를 사용했다.

이 두 가지 덕분에, 기존 다익스트라 알고리즘보다 시간을 단축할 수 있었던 것이다. 그리고 이 알고리즘은 BFS(너비우선탐색) 알고리즘과 굉장히 유사하다. 큐에서 뺀 값을 기준으로 탐색하는 방식이 매우 유사하다.