(cpp) Baekjoon 1753번 문제 ‘최단경로’ - 그래프 이론, 다익스트라
Baekjoon 1753번 문제 ‘최단경로’ - 그래프 이론, 다익스트라
- 다익스트라 이해하기
예제입력에 대한 문제풀이
1. 시작점 외에는 아직 아무곳도 방문하지 않은 상태이므로 시작점 외에 가상의 어떤 점이 있다고 생각하고 그 점이 시작점과 가중치 없이 연결되어 있다고 생각하면 dist[시작점] = 0 이라 할 수 있다. 반면, 시작점을 제외한 나머지 점들에 대해 dist[2],dist[3],dist[4],dist[5]는 전부 INF로 넣어준다.
2. 그러면 이제 시작지점인 1번 노드에 온 상태이며 현재까지 가중치는 0이다(가상의 점에서 온 것으로 생각하므로). 이제, 1번 노드에서 갈 수 있는 후보군을 추려야한다. 1번과 직접 연결되어 있는 2번 3번이 후보군이 될 수 있고, 차례대로 방문하면서 최단경로를 갱신한다. 먼저, 1번에서 2번 방문시 가중치는 0+2가 된다(가상의 지점에서 시작점까지의 가중치를 0이라 보고, 1에서 2까지의 가중치가 2이므로 합쳐서 2). 2가 기존의 dist[2] = INF보다 당연히 작기 때문에 dist[2]=2로 갱신한다. 그 다음, 1에서 3으로 가는 경우를 살펴보면 가중치가 0+3이된다. 3 또한 기존의 dist[3] = INF보다 당연히 작기 때문에 dist[3] = 3으로 갱신한다. 이때, 주의할 점은 1번 지점에서 갈 수 있는 후보군이 2,3 두 개 였으므로 그 다음 단계에서는 2또는 3을 새로운 시작점으로 해야한다. 따라서,1에서 2로 가는 최단경로와 1에서 3으로 가는 최단경로를 구하는 각각의 단계 마지막에 새로운 시작점을 갱신하는 큐가 필요하다. 즉, 큐에는 [2까지 오는데 걸린 경로, 현재 위치],[3까지 오는데 걸린 경로, 현재위치]가 입력되어 있다. 큐 = [[2,2],[3,3]]
3. 시작점 1은 벗어났고 이제 2를 새로운 시작점으로 했을 때 갈 수 있는 최단경로와 3을 시작점으로 했을 때 갈 수 있는 최단경로를 각각 파악하면 된다. 이는 위의 과정을 반복하면 된다. 2가 새로운 시작점인 경우 현재 2까지 오는데 걸린 총 비용은 2이고, 2에서 갈 수 있는 후보군인 3과 4는 각각 4,5의 가중치를 갖는다. 이때, 3으로 가는 경우 dist[3] = 2+4 = 6인데, 기존 dist[3]=3과 비교하면 최단 경로가 아니므로 갱신하지 않는다. 4로가는 경우 기존 dist[4]=INF보다 작으므로 dist[4] = 2+5 = 7로 갱신한다. 마찬가지로 다음 단계를 위한 시작점을 갱신한다. 큐 =[[3,3][7,4]]
4. 현재까지 1,2,3,4를 방문했고 dist[1]=0,dist[2]=2,dist[3]=3,dist[4]=7 인 상황이다. 다음은 3을 새로운 시작점으로 했을 경우를 본다. 3에서 갈 수 있는 후보군은 4 하나인데, 3까지 오는데 들었던 총비용(dist[3])은 3이고 3에서 4로가는 비용은 6이므로 dist[4]=3+6=9가 되겠지만, 이미 윗 단계에서 dist[4]=7로 갱신했으며 이는 9보다 최단경로 이므로 9로 갱신하지 않고 그대로 둔다. 큐 = [[7,4]]
5. 이제 노드 4번 위치까지 와있으며 4를 새로운 시작점으로 했을 때 갈 수 있는 경로는 없다. While문이 돌아도 q가 새로 채워지지 않으므로 q가 비고 while문이 끝난다. 노드 5번은 초기 설정인 dist[5] = INF를 그대로 유지한 채이다.
코드
#define _CRT_SECURE_NO_WARNINGS
#define INF 100000000
#include<iostream>
#include<queue>
#include<vector>
using namespace std;
int v, e, k,from,to,w;
int dist[20001]; //각 정점까지 가는데 드는 최소비용
vector<pair<int, int>> g[20001];
void solution() {
priority_queue<pair<int, int>> q;
q.push(make_pair(0, k));
dist[k] = 0;
while (!q.empty()){
int cost =-q.top().first; //지금까지 오는데 든 총 비용, 우선순위큐는 기본적으로 큰 값이 우선순위를 가짐
//따라서 - 붙이면 작은 값이 우선순위 갖게됨
// 2보다 3이 우선순위, 그런데 우린 2가 더 우선순위 여야함
// -2 -3 로 넣으면 -2가 더 우선순위가 됨!
int cur = q.top().second; //현재 위치
q.pop(); //현재 위치만 기억하고 비우기
for (int i = 0; i < g[cur].size(); i++) {
int next = g[cur][i].first; //다음 노드= 현재위치에서 갈 수 있는 후보군
int ncost = g[cur][i].second; //현재 위치에서 다음 노드까지 가는 비용
if (dist[next] > cost + ncost) {
dist[next] = cost + ncost;
q.push(make_pair(-dist[next], next));
}
}
}
for (int i = 1; i <= v; i++) {
if (dist[i] == INF) {
cout << "INF" << '\n';
}
else {
cout << dist[i] <<'\n';
}
}
}
int main() {
cin >> v >> e;
cin >> k;
for (int i = 0; i < e; i++) {
cin >> from >> to >> w;
g[from].push_back(make_pair(to, w));
}
for (int i = 1; i <= v; i++) {
dist[i] = INF;
}
solution();
}
- 두 도시 사이에 경로가 2개 이상 있을 수 있으므로 시작큐에서 현재 위치를 꺼낼 때 더 작은 가중치와 짝지어진 번호를 뽑아야 한다. 이 때 우선 순위 큐를 활용할 수 있는데, 기존 우선순위 큐는 큰 수가 더 우선순위이므로 마이너스를 붙여주어 조작이 필요 .