출처 :
최단경로 성공 풀이
| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞은 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 1 초 | 128 MB | 19875 | 5620 | 2761 | 25.433% |
문제
방향그래프가 주어지면 주어진 시작점에서 다른 모든 정점으로의 최단 경로를 구하는 프로그램을 작성하시오. 단, 모든 간선의 가중치는 10 이하의 자연수이다.
입력
첫째 줄에 정점의 개수 V와 간선의 개수 E가 주어진다. (1≤V≤20,000, 1≤E≤300,000) 모든 정점에는 1부터 V까지 번호가 매겨져 있다고 가정한다. 둘째 줄에는 시작 정점의 번호 K(1≤K≤V)가 주어진다. 셋째 줄부터 E개의 줄에 걸쳐 각 간선을 나타내는 세 개의 정수 (u, v, w)가 순서대로 주어진다. 이는 u에서 v로 가는 가중치 w인 간선이 존재한다는 뜻이다. u와 v는 서로 다르며 w는 10 이하의 자연수이다. 서로 다른 두 정점 사이에 여러 개의 간선이 존재할 수도 있음에 유의한다.
출력
첫째 줄부터 V개의 줄에 걸쳐, i번째 줄에 i번 정점으로의 최단 경로의 경로값을 출력한다. 시작점 자신은 0으로 출력하고, 경로가 존재하지 않는 경우에는 INF를 출력하면 된다.
예제 입력
5 6 1 5 1 1 1 2 2 1 3 3 2 3 4 2 4 5 3 4 6
예제 출력
0 2 3 7 INF
힌트
출처
- 빠진 조건을 찾은 사람: algoshipda
- 문제를 만든 사람: author5
>> 해설
위 문제는 다익스트라를 이용하는 문제이다.
벨만 포드의 시간 복잡도는 O(|V|*|E|) 이기 때문에 20,000 x 300,000 는 너무 숫자가 커서 시간 복잡도를 초과한다.
다익스트라는 배웠지만 실제 응용은 처음이라서 구현에 엄청난 시간이 소요되었다.
문제를 계속 풀어보니 시간 초과 문제가 발생했다.
너무 오래 고민하다가 다른 소스코드를 많이 살펴보게 되었고, 그 후 나무위키를 살펴보니 정확히 문제를 알게 되었다.
나무위키 출처 : 에츠허르 다익스트라가 고안한 알고리즘으로, 그가 처음 고안한 알고리즘은 O(V2)의 시간복잡도를 가졌다. 이후 우선순위 큐(=힙 트리)등을 이용한 더욱 개선된 알고리즘이 나오며, O(ElogV)의 시간복잡도를 가지게 되었다.
O(ElogV) 의 시간복잡도를 가지는 이유는 힙에 최악의 경우 E번의 탐색한 노드를 집어넣는 경우가 발생하게 되는데, 이러한 경우에 O(ElogE)의 시간 복잡도가 나오며, 중복 간선을 허용하지 않는 그래프라면 O(E) <= O(V2) 이므로 O(log E) <= O(log V2)와 같다. 이때 O(logV2)=O(2×logV) 이므로, 상수를 제거하면 O(ElogV)가 된다. 물론 여기서 탐색에 소요되는 시간 O(V+E)는 O(ElogV)보다 작으므로 무시한다.
알고리즘 문제를 풀다가 보니, V2은 1억이 넘기 때문에 알고리즘 문제를 풀기에 부적절했다.
우선순위 큐를 이용하면 300,000 * log(20,000) 이기 때문에 충분한 속도로 문제를 해결할 수 있다.
따라서, 이 문제는 우선 순위 큐를 이용하여 구현해야 한다.
여러 가지 소스 코드를 보다가 가장 간단해 보이는 걸로 참고했다.
+ 문제를 풀다보니 자꾸 "틀렸습니다" 가 나왔는데, 중간에 == 이 없어서 생긴 문제였다.
이런 문제 때문에 시간이 상당히 먹으면 안되는데... 어떻게 찾을 수도 없고
어쩔 수 없는 문제인데 해결 할 수 없는 문제 같다.
>> 벡터를 사용한 실패한 소스 코드
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 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 | #include <iostream> #include <vector> #define INF 987654321 #define MAX_V 20001 #define MAX_E 300001 using namespace std; int start_node_num, V, E; typedef struct NODE { int end; int val; }; // 각 노드의 엣지를 저장하는 벡터 // 0번 인덱스는 버린다. vector<NODE> EDGE_arr[MAX_E]; // 출발 노드에서부터의 거리를 저장하는 배열 int route_val[MAX_V] = { 0 }; int isUsed[MAX_V] = { 0 }; void dijkstra() { int now_node = start_node_num; isUsed[now_node] = 1; vector<int> can_change_node_vec; // 노드의 거리 갱신은 V-1 번 만큼 하면 된다. for (int not_use = 0; not_use < V-1; not_use++){ isUsed[now_node] = 1; // 현재 노드에서 부터 주변에 있는 얘들의 값을 갱신한다. for (int k = 0; k < EDGE_arr[now_node].size(); k++) { int new_val = route_val[now_node] + EDGE_arr[now_node][k].val; int before_val = route_val[EDGE_arr[now_node][k].end]; // 현재 노드로 부터 연결된 엣지의 목적지까지 가는 거리와 기존의 거리를 비교하여, // 기존의 것이 더 크면 값을 갱신한다. if (new_val < before_val) { route_val[EDGE_arr[now_node][k].end] = new_val; can_change_node_vec.push_back(EDGE_arr[now_node][k].end); } } int sub_start_node = -1; int sub_index = -1; for (int i = 0; i < can_change_node_vec.size(); i++) { if ( !isUsed[can_change_node_vec[i]] ) { // 만약 다음 노드가 정해지지 않았으면, 다음 노드를 결정한다. if (sub_start_node == -1) sub_start_node = can_change_node_vec[i]; // 다음 노드가 결정 되어 있으면 비교해서 변경한다. else { // 만약 최소 노드가 다시 발견되면 갱신한다. if (route_val[sub_start_node] > route_val[can_change_node_vec[i]]) { sub_index = i; sub_start_node = can_change_node_vec[i]; } } } } if (sub_index != -1) can_change_node_vec.erase(can_change_node_vec.begin() + sub_index); // 다음 노드 갱신 now_node = sub_start_node; } } int main(){ cin >> V >> E >> start_node_num; int from, to, val; // 간선 연결 for (int i = 0; i < E; i++) { scanf("%d %d %d", &from, &to, &val); int isExist = 0; // 간선간의 중복을 제거하기 위한 구문 for (int j = 0; (j < EDGE_arr[from].size()) && (!isExist); j++) { // 지금 노드가 더 작거나 같으면 교체한다. if ((EDGE_arr[from][j].end == to) && EDGE_arr[from][j].val >= val) { EDGE_arr[from][j].val = val; isExist = 1; } } // 존재하지 않으면 밀어 넣는다. if (isExist == 0) EDGE_arr[from].push_back(NODE{ to, val }); } // 간선간의 거리 초기화 for (int i = 1; i <= V; i++) { route_val[i] = INF; } route_val[start_node_num] = 0; // 벨만-포드 알고리즘은 복잡도가 O(V*E) 이기 때문에, 이 문제에서는 너무 크다. // 다익스트라 알고리즘을 진행한다. dijkstra(); // 값을 출력한다. for (int i = 1; i <= V; i++) { if (route_val[i] != INF) printf("%d\n", route_val[i] ); else printf("INF\n"); } return 0; } | cs |
>> 우선 순위 큐를 사용한 성공한 소스 코드
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 74 75 76 77 | #include <iostream> #include <vector> #include <queue> #define INF 987654321 #define MAX_V 20001 #define MAX_E 300001 using namespace std; int start_node_num, V, E; typedef struct NODE { int end; int val; }; // 각 노드의 엣지를 저장하는 벡터 // 0번 인덱스는 버린다. vector<NODE> EDGE_arr[MAX_E]; // 출발 노드에서부터의 거리를 저장하는 배열 int dist[MAX_V] = { 0 }; void dijkstra() { priority_queue< pair<int,int> > pq; pq.push({ 0, start_node_num }); // 노드의 거리 갱신은 V-1 번 만큼 하면 된다. while (!pq.empty()){ int now_node = pq.top().second; int cost = -1 * pq.top().first; pq.pop(); // 현재 노드에서 부터 주변에 있는 얘들의 값을 갱신한다. for (int k = 0; k < EDGE_arr[now_node].size(); k++) { int new_val = dist[now_node] + EDGE_arr[now_node][k].val; int before_val = dist[EDGE_arr[now_node][k].end]; // 현재 노드로 부터 연결된 엣지의 목적지까지 가는 거리와 기존의 거리를 비교하여, // 기존의 것이 더 크면 값을 갱신한다. if (new_val < before_val) { dist[EDGE_arr[now_node][k].end] = new_val; pq.push({ -1*new_val, EDGE_arr[now_node][k].end }); } } } } int main(){ cin >> V >> E >> start_node_num; int from, to, val; // 간선 연결 for (int i = 0; i < E; i++) { scanf("%d %d %d", &from, &to, &val); EDGE_arr[from].push_back(NODE{ to, val }); } // 간선간의 거리 초기화 for (int i = 1; i <= V; i++) { dist[i] = INF; } dist[start_node_num] = 0; // 벨만-포드 알고리즘은 복잡도가 O(V*E) 이기 때문에, 이 문제에서는 너무 크다. // 다익스트라 알고리즘을 진행한다. dijkstra(); // 값을 출력한다. for (int i = 1; i <= V; i++) { if (dist[i] != INF) printf("%d\n", dist[i] ); else printf("INF\n"); } return 0; } | cs |
- 출처 -