백준 온라인 저지의 1916번 최소비용 구하기 문제입니다.
[링크] https://www.acmicpc.net/problem/1916
문제 조건과 설명
N개의 도시가 있다. 그리고 한 도시에서 출발하여 다른 도시에 도착하는 M개의 버스가 있다. 우리는 A번째 도시에서 B번째 도시까지 가는데 드는 버스 비용을 최소화 시키려고 한다. A번째 도시에서 B번째 도시까지 가는데 드는 최소비용을 출력하여라. 도시의 번호는 1부터 N까지이다.
Input
첫째 줄에 도시의 개수 N(1 ≤ N ≤ 1,000)이 주어지고 둘째 줄에는 버스의 개수 M(1 ≤ M ≤ 100,000)이 주어진다. 그리고 셋째 줄부터 M+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그 버스의 출발 도시의 번호가 주어진다. 그리고 그 다음에는 도착지의 도시 번호가 주어지고 또 그 버스 비용이 주어진다. 버스 비용은 0보다 크거나 같고, 100,000보다 작은 정수이다.
그리고 M+3째 줄에는 우리가 구하고자 하는 구간 출발점의 도시번호와 도착점의 도시번호가 주어진다. 출발점에서 도착점을 갈 수 있는 경우만 입력으로 주어진다.
Output
첫째 줄에 출발 도시에서 도착 도시까지 가는데 드는 최소 비용을 출력한다.
생각한 아이디어
다익스트라 알고리즘을 구현해서 풀어야 하는 문제입니다.
그런데 시간 제한이 0.5초밖에 되지 않습니다. 따라서 시간복잡도 측면에서 더 효율적인 우선순위 큐(min heap)를 사용한 다익스트라 알고리즘을 구현하여야 합니다.
시간복잡도 측면에서 더 효율적인 이유는 다음과 같습니다.
다익스트라 알고리즘은 특정 시작점을 기준으로 거리(간선의 가중치)가 가장 짧은 정점을 찾아 다음 과정을 진행해야 합니다.
즉 아직 처리하지 않은 노드 중에 거리가 최소인 노드 찾기를 효율적으로 탐색해야 합니다.
우선순위 큐를 사용하지 않는 코드에서는, 특정 정점을 기준으로 모든 정점들을 탐색하면서 최소 거리를 찾아야 했습니다.
이 경우, 정점이 100만개라면 100만*100만 번의 탐색이 필요하게 됩니다. (즉, O(V^2))
1 2 3 4 5 6 7 8 9
... // 모든 정점들에 대한 반복문 for(int i = 1; i <= 정점의 갯수; i++){ // 정점 i에 대해 최소 거리인 정점 j를 찾기 위한 반복분 for (int j = 1; j <= 정점의 갯수; j++){ ... } }
만약 정점이 100만개이고, 간선은 한 개나 두 개 정도이면 정말로 비효율적인 코드가 될 것입니다.
연결된 길은 고작 한 두개인데, 정점이 너무 많아서 일일이 다 찾아보고 있는 상황이 발생합니다.
- 하지만 우선순위 큐를 사용하면 항상 맨 앞에 최솟값이 들어가도록 유지할 수 있습니다.
- 그러므로, 큐의 pop 연산만으로도 최소 거리에 있는 정점을 한번에 선택할 수 있게 됩니다.
- 이 경우, 시간복잡도는 O(ElogV) 가 됩니다.
- (단, 간선의 갯수가 매우 많은 경우에는 O(V^2) 형태의 시간복잡도가 더 효율적일 수도 있을 것입니다.)
구현의 전반적인 과정은 아래 포스팅을 참고해 주시면 될 것 같습니다.
다익스트라 알고리즘 : https://chanhuiseok.github.io/posts/algo-47/
vec 에는 특정 정점과 연결된 정점, 그리고 그 연결된 정점 사이의 간선 가중치(거리값) 가 저장됩니다.
예) 간선 정보를 입력받을 때 아래와 같이 입력받았을 경우
1 2 2
1 3 5
…
1 2 3
vec[1][0] 에는 {2, 2} pair가 들어가 있음 vec[1][1] 에는 {3, 5} pair가 들어가 있음 -> 즉, vec[1](1번 정점)에 연결된 간선 정보들이 차례로 push되어 저장
특정 정점에서의 최소 거리를 가지는 정점을 찾는 부분을 소스코드 상에 추가로 구현하면 되는데, 그것을 C++의 priority queue 를 활용해서 구현하였습니다. 아래 소스 코드에서 dijkstra 함수를 보시면 됩니다.
C++에서 제공하는 priority queue는 기본적으로 큰 것이 앞에 오도록 하는 max heap 입니다.
따라서 거리 값(가중치)이 작은 것이 앞에 오도록 하려면, 큐에 push할 때 거리에 * -1을 한 음수값을 넣어야 최소 거리를 갖는 정점을 바로 확인할 수 있습니다.
다익스트라 알고리즘은 이미 처리한 정점에 대해서는 skip 해야 하므로 visit 배열과 같은 것이 필요하지만, 우선순위 큐를 이용하여 짤 경우에는 아래 코드가 그 과정을 대신할 수 있습니다.
1 2
// 이미 담겨 있는 것보다 distance가 크면 넘어간다. if (dist[cur] < distance) continue;
- 큐에서 꺼낸 맨 앞의 원소 {distance, cur} 의 distance 값이, dist[cur] 값보다 크면 이미 cur 정점은 처리가 완료되었음을 알 수 있습니다. 따라서 continue; 로 skip할 수 있게 해 주므로, 항상 최소 거리를 가지는 값을 얻을 수 있습니다.
소스코드
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
#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>
#define INF 987654321
using namespace std;
int dist[1001];
vector<pair<int, int>> vec[100001];
void dijkstra(int start) {
dist[start] = 0; // 처음 위치는 0
priority_queue<pair<int, int>>pq;
pq.push({ dist[start] , start });
while (!pq.empty()) {
int cur = pq.top().second; // 큐의 가장 맨 앞에 있는 정점의 번호를 담아온다.
int distance = pq.top().first * -1;
pq.pop();
// 이미 담겨 있는 것보다 distance가 크면 넘어간다.
if (dist[cur] < distance) continue;
// 선택한 노드의 모든 인접 노드들을 확인한다.
for (int i = 0; i < vec[cur].size(); i++) {
int next = vec[cur][i].first;
int nextDistance = distance + vec[cur][i].second;
// 다음 것과 기존의 비용과 비교
if (nextDistance < dist[next]) {
dist[next] = nextDistance;
pq.push({nextDistance * -1 , next});
}
}
}
}
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
int start, end;
int N, M;
cin >> N; // 정점 갯수
cin >> M; // 간선 갯수
for (int i = 1; i <= N; i++)
dist[i] = INF;
for (int i = 0; i < M; i++) {
int u, v, w;
cin >> u >> v >> w;
vec[u].push_back({ v,w });
}
cin >> start; // 시작점
cin >> end; // 도착점
dijkstra(start);
cout << dist[end];
return 0;
}