궤도
[백준] 1753번 : 최단경로 본문
문제
풀이
TMI
난 사실 다익스트라 알고리즘에 트라우마가 있다. 바로 지금보다도 훨씬 아무것도 모르던 2학년 2학기 시절 라이브러리 하나 없이 다익스트라 알고리즘을 구현해야 했던 것이다. 심지어 최단 거리만 출력하는게 아니라 경로도 출력해야 했다.
c로 구현해야 했기 때문에 스택, 우선순위 큐 기타 등등을 스스로 구현해야 했다.
하지만 난 이제 라이브러리를 마음껏 사용할 수 있기 때문에 용기를 내보려 한다.
다익스트라 알고리즘은 특정한 출발 노드에서 모든 노드로 가는 최단거리를 구하는 알고리즘이다.
힙을 사용했을 때의 시간복잡도는 O(|E|log|V|)라고 한다. log의 밑은 2다.
이런 알고리즘이다.
BFS+그리디 알고리즘이라고 생각하면 편할 것 같다.
BFS처럼 큐에 값을 넣지만, 가중치가 작은 것을 우선으로 그리디하게 뽑는다.
솔직히 이론은 나보다 잘 설명하는 사람이 넘치고 넘쳤으니 난 코드와 함께 설명하겠다.
결국 tmi가 더 길었다.
소스코드
#include <iostream>
#include <vector>
#include <queue>
#include <utility>
#include <algorithm>
using namespace std;
const int INF = 1e9;
typedef pair<int, int> pp;
vector<vector<pp>> graph; //graph[i][j].first = dest, graph[i][j].second = weight
vector<int> V_dist; //INF로 초기화
vector<bool> visited; //방문 체크
priority_queue<pp, vector<pp>, greater<pp>> min_dist; //min-heap, min_dist.first = distance, min_dist.second = source
void dijkstra(int start) {
int new_dist;
V_dist[start] = 0; //시작점의 거리는 0
min_dist.push(make_pair(V_dist[start], start)); //거리와 source 투입
while (!min_dist.empty()) { //우선순위 큐가 비어있지 않을 때
int dist = min_dist.top().first; //현재 노드 까지의 최단 거리
int source = min_dist.top().second; //노드
min_dist.pop();
if (!visited[source]) { //방문한 적 없는 노드라면
for (int i = 0; i < graph[source].size(); i++) { //해당 노드가 source인 모든 정점(dest)
new_dist = dist + graph[source][i].second; //현재 노드까지의 최단거리 + source에서 dest까지의 weight
if (new_dist < V_dist[graph[source][i].first]) { //이 값이 기존의 V_dist[dest]보다 작다면
V_dist[graph[source][i].first] = new_dist; //dest의 최단거리 갱신
min_dist.push(make_pair(new_dist, graph[source][i].first)); //우선순위 큐에 거리와 dest 노드 정보 삽입
}
}
}
visited[source] = true; //source 노드 방문 처리
}
}
int main() {
ios::sync_with_stdio(false);
cin.tie(NULL);
int V, E, K, s, d, w;
cin >> V >> E >> K;
graph.assign(V + 1, vector<pp>(0));
V_dist.assign(V + 1, INF);
visited.assign(V + 1, false);
for (int i = 0; i < E; i++) {
cin >> s >> d >> w;
graph[s].push_back(make_pair(d, w));
}
dijkstra(K);
for (int i = 1; i <= V; i++) {
if (V_dist[i] == INF)
cout << "INF\n";
else
cout << V_dist[i] << '\n';
}
}전체 소스코드다. 이게 총 62줄인데 라이브러리 없이 구현했던 코드를 지금 확인해보니 220줄 정도 된다. 어휴
const int INF = 1e9;
typedef pair<int, int> pp;일단 무한대인 INF를 설정하고 페어를 많이 사용할거라 편하게 typedef 했다.
vector<vector<pp>> graph; //graph[i][j].first = dest, graph[i][j].second = weight
vector<int> V_dist; //INF로 초기화
vector<bool> visited; //방문 체크
priority_queue<pp, vector<pp>, greater<pp>> min_dist; //min-heap, min_dist.first = distance, min_dist.second = sourcegraph 벡터에는 각 정점들 사이의 간선 존재 여부와 그 가중치를 저장한다.
graph[1]에 (3, 2)라는 값이 있다면, 정점 1부터 3으로 가는 가중치 2의 단방향 간선이 있단 뜻이다.
V_dist[i]에는 시작 정점으로부터 i 정점까지의 최단 거리를 저장할 것이다. 초기값은 INF이다.
visited에는 각 정점의 방문여부를 저장한다.
그리고 min_dist는 갈 수 있는 모든 간선을 저장하는 우선순위 큐다. min-heap으로 구현했기 때문에 간선의 가중치가 가장 작은 것이 먼저 나올 것이다.
간선의 가중치라고 표현했지만 엄밀히 말하면 (시작 정점으로부터 정점 i까지의 최단거리) +(i->j의 간선 가중치)이다.
다익스트라는 시작 정점이라는 기준이 있기 때문에 정점들간의 가중치보다 시작 정점까지의 거리가 더 중요하다.
cin >> V >> E >> K;
graph.assign(V + 1, vector<pp>(0));
V_dist.assign(V + 1, INF);
visited.assign(V + 1, false);
for (int i = 0; i < E; i++) {
cin >> s >> d >> w;
graph[s].push_back(make_pair(d, w));
}
dijkstra(K);벡터들의 크기를 할당하고 간선정보를 graph에 넣은 뒤, 시작 정점 K에 대한 다익스트라 알고리즘을 호출한다.
void dijkstra(int start) {
int new_dist;
V_dist[start] = 0; //시작점의 거리는 0
min_dist.push(make_pair(V_dist[start], start)); //거리와 source 투입
while (!min_dist.empty()) { //우선순위 큐가 비어있지 않을 때
int dist = min_dist.top().first; //현재 노드 까지의 최단 거리
int source = min_dist.top().second; //노드
min_dist.pop();
if (!visited[source]) { //방문한 적 없는 노드라면
for (int i = 0; i < graph[source].size(); i++) { //해당 노드가 source인 모든 정점(dest)
new_dist = dist + graph[source][i].second; //현재 노드까지의 최단거리 + source에서 dest까지의 weight
if (new_dist < V_dist[graph[source][i].first]) { //이 값이 기존의 V_dist[dest]보다 작다면
V_dist[graph[source][i].first] = new_dist; //dest의 최단거리 갱신
min_dist.push(make_pair(new_dist, graph[source][i].first)); //우선순위 큐에 거리와 dest 노드 정보 삽입
}
}
}
visited[source] = true; //source 노드 방문 처리
}
}다익스트라 알고리즘이다.
V_dist[start] = 0; //시작점의 거리는 0
min_dist.push(make_pair(V_dist[start], start)); //거리와 source 투입먼저 시작정점 자신과의 거리는 0이니까 V_dist[start]를 0으로 한다.
그리고 V_dist[start]와 start를 우선순위 큐에 넣는다. 시작점이 1이라면 (0, 1)이 들어간다.
while (!min_dist.empty()) { //우선순위 큐가 비어있지 않을 때
int dist = min_dist.top().first; //현재 노드 까지의 최단 거리
int source = min_dist.top().second; //노드
min_dist.pop();
if (!visited[source]) { //방문한 적 없는 노드라면
for (int i = 0; i < graph[source].size(); i++) { //해당 노드가 source인 모든 정점(dest)
new_dist = dist + graph[source][i].second; //현재 노드까지의 최단거리 + source에서 dest까지의 weight
if (new_dist < V_dist[graph[source][i].first]) { //이 값이 기존의 V_dist[dest]보다 작다면
V_dist[graph[source][i].first] = new_dist; //dest의 최단거리 갱신
min_dist.push(make_pair(new_dist, graph[source][i].first)); //우선순위 큐에 거리와 dest 노드 정보 삽입
}
}
}
visited[source] = true; //source 노드 방문 처리우선순위 큐가 텅 빌 때까지 while문을 돈다.
int dist = min_dist.top().first; //현재 노드 까지의 최단 거리
int source = min_dist.top().second; //노드
min_dist.pop();source에 정점 A가 들어왔다면, dist는 시작 정점으로부터 정점 A까지의 최단 거리이다.
if (!visited[source]) { //방문한 적 없는 노드라면
for (int i = 0; i < graph[source].size(); i++) { //해당 노드가 source인 모든 정점(dest)
new_dist = dist + graph[source][i].second; //현재 노드까지의 최단거리 + source에서 dest까지의 weight
if (new_dist < V_dist[graph[source][i].first]) { //이 값이 기존의 V_dist[dest]보다 작다면
V_dist[graph[source][i].first] = new_dist; //dest의 최단거리 갱신
min_dist.push(make_pair(new_dist, graph[source][i].first)); //우선순위 큐에 거리와 dest 노드 정보 삽입
}
}
}이 source 정점이 방문한 적 없는 정점인지 확인해야 한다. 큐에 같은 정점이 여러번 들어갔을 수도 있기 때문이다.
그리고 source와 연결된 정점들을 확인한다. A->B로 가는 간선이 있다고 하자.
dist=10이고 A->B 간선의 가중치는 3이라고 할 때, V_dist[B]=15라고 한다.
10+3<15이다. 이 뜻은 시작 정점으로부터 B 정점으로 가는 기존의 방법보다 시작 정점->A->B의 거리가 더 짧단 거다.
그럴 땐 V_dist[B]의 값을 갱신하고 이 값과 B를 큐에 삽입한다. 위 예에선 (13, B)가 들어갈 것이다.
visited[source] = true; //source 노드 방문 처리마지막으로 정점 source를 방문 처리한다.
for (int i = 1; i <= V; i++) {
if (V_dist[i] == INF)
cout << "INF\n";
else
cout << V_dist[i] << '\n';
}출력하면 끝
