1753 - 최단경로
본문
방향그래프가 주어지면 주어진 시작점에서 다른 모든 정점으로의 최단 경로를 구하는 프로그램을 작성하시오. 단, 모든 간선의 가중치는 $10$ 이하의 자연수이다.
입력
첫째 줄에 정점의 개수 $V$와 간선의 개수 $E$가 주어진다. ($1 \leq V \leq 20\,000, 1 \leq E \leq 300\,000$) 모든 정점에는 $1$부터 $V$까지 번호가 매겨져 있다고 가정한다. 둘째 줄에는 시작 정점의 번호 $K$($1 \leq K \leq V$)가 주어진다. 셋째 줄부터 $E$개의 줄에 걸쳐 각 간선을 나타내는 세 개의 정수 ($u, v, w$)가 순서대로 주어진다. 이는 $u$에서 $v$로 가는 가중치 $w$인 간선이 존재한다는 뜻이다. $u$와 $v$는 서로 다르며 $w$는 $10$ 이하의 자연수이다. 서로 다른 두 정점 사이에 여러 개의 간선이 존재할 수도 있음에 유의한다.
출력
첫째 줄부터 $V$개의 줄에 걸쳐, $i$번째 줄에 $i$번 정점으로의 최단 경로의 경로값을 출력한다. 시작점 자신은 0으로 출력하고, 경로가 존재하지 않는 경우에는 INF를 출력하면 된다.
제한
| 시간 제한 | 메모리 제한 |
|---|---|
| 1sec | 256MB |
풀이
“그래프에서의 최단경로 문제” + “간선의 가중치가 양수” 인 문제라면, 다익스트라 알고리즘을 통해 문제를 쉽게 해결할 수 있다. 그래서, 다익스트라 알고리즘을 그대로 가져온다면 문제를 해결할 수 있는 기본형 문제라고 볼 수 있다.
다만 C로 구현한다면 문제가 좀 생기는데, 정점의 개수가 최대 2만개이기 때문에, 인접 행렬로 그래프를 구현하면 메모리 문제를 맞닥뜨린다. 다행히도 간선의 개수는 최대 30만개이므로, 간선의 정보를 기록하는 인접 리스트 방법을 이용하면 메모리 문제는 해결할 수 있다. 하지만, 서로 다른 두 정점 사이에도 여러 개의 간선이 존재할 수 있다고 한다. 즉 같은 정점을 연결하는 간선이 여러 개 존재할 수 있다는 의미고, 인접 리스트는 이것들을 모두 기록하고 있을 것이다. 최단경로 문제에서는 이런 간선들 중 최소의 가중치를 가지는 간선 하나만 필요한데, 걸러낼 수 있는 방법이 딱히 없어서 시간적인 손해를 감수할 수 밖에 없다는 것. 그렇다면 다른 부분에서 시간 손해를 메꿔야 할 것이다.
그래서 다익스트라 알고리즘에서는 시간을 최대한 줄이는 방법을 택할 것이다. 선택한 방법은 크게 2가지가 있다.
인접리스트에 저장되는 간선들 중, 출발점이 다익스트라 알고리즘의 시작점과 같은 경우, 다익스트라 초기화 과정 전에 미리 간선 정보를 적용하여 시작점으로부터 갈 수 있는 경로들의 정보는 미리 업데이트한다
매 라운드마다 가중치가 최소인 정점을 선택하는 과정에서, 우선순위 큐를 이용하여 최소 정점을 선택한다
1번 선택의 경우, 여러 개 입력되는 간선들의 정보들 중 최소의 간선만 미리 한 번 계산해둘 수 있다는 점에서 시간을 절약할 수 있다. 2번 선택의 경우, 기존의 $O(N)$의 정점 선택 방법을 $O(\log N)$의 시간으로 줄일 수 있는 만큼, 가장 획기적으로 시간을 절약할 수 있는 전략이다.
그래서, 구현 관점에서는 크게 3가지로 분류할 수 있다.
- 입력된 간선의 정보들을 기록할 인접 리스트 그래프
- 다익스트라 알고리즘
- 라운드마다의 최소 정점을 선택하기 위한 우선순위 큐 구조
이것들을 유기적으로 연결하면 답을 얻을 수 있다.
코드
사용 언어 : C
최종 수정일 : 2023 / 10 / 31
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
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
#include <stdio.h>
#include <stdlib.h>
typedef char bool;
const bool true = 1;
const bool false = 0;
typedef struct Edge {
int d;
int v;
struct Edge* next;
} ED;
typedef struct HeapNode {
int s;
int v;
} HN;
#define MAX_VET 20000
const int INF = 987654321;
ED* grid[MAX_VET + 1];
int start;
int n, e;
int result[MAX_VET + 1];
HN heap[MAX_VET * 10];
int top;
void insertEdge(int a, int b, int c) {
ED* newNode = (ED*)malloc(sizeof(ED));
newNode->d = b;
newNode->v = c;
newNode->next = grid[a];
grid[a] = newNode;
return;
}
void insertHeap(HN x) {
heap[++top] = x;
int i = top;
while (i > 1 && heap[i / 2].v > x.v) {
heap[i] = heap[i / 2];
heap[i / 2] = x;
i /= 2;
}
return;
}
HN popHeap() {
HN ret = heap[1];
heap[1] = heap[top--];
int i = 1, tp = 2;
while (tp < top) {
if (heap[tp].v > heap[tp + 1].v) {
++tp;
}
if (heap[i].v <= heap[tp].v) {
break;
}
HN temp = heap[i];
heap[i] = heap[tp];
heap[tp] = temp;
i = tp, tp *= 2;
}
if (tp == top && heap[i].v > heap[tp].v) {
HN temp = heap[i];
heap[i] = heap[tp];
heap[tp] = temp;
}
return ret;
}
int main() {
scanf("%d %d", &n, &e);
scanf("%d", &start);
for (int i = 1; i <= n; ++i) {
result[i] = INF;
}
while (e--) {
int a, b, c;
scanf("%d %d %d", &a, &b, &c);
insertEdge(a, b, c);
if (a == start && c < result[b]) {
result[b] = c;
}
}
result[start] = 0;
for (int i = 1; i <= n; ++i) {
insertHeap((HN){i, result[i]});
}
while (top > 0) {
HN cn = popHeap();
if (cn.v > result[cn.s]) {
continue;
}
ED* cur = grid[cn.s];
while (cur != NULL) {
if (cn.v + cur->v < result[cur->d]) {
result[cur->d] = cn.v + cur->v;
insertHeap((HN){cur->d, result[cur->d]});
}
cur = cur->next;
}
}
for (int i = 1; i <= n; ++i) {
if (result[i] == INF) {
printf("INF\n");
} else {
printf("%d\n", result[i]);
}
}
return 0;
}