[다익스트라 알고리즘] (C/C++) 백준 - 5972번

다익스트라(Dijkstra) 알고리즘은 동적 계획법을 활용한 대표적인 최단 경로 탐색 알고리즘(Shortest Path)이다. 흔히 인공위성 GPS 소프트웨어 등에서 가장 많이 사용된다.

 

다익스트라 알고리즘은 특정한 하나의 정점에서 다른 모든 정점으로 가는 최단 경로를 알려준다.

 

다만 이 때 음의 간선을 포함할 수 없다. 다익스트라 알고리즘이 동적 계획법과 관련되어 있는 이유는 최단 거리는 여러 개의 최단 거리로 이루어져있기 때문이다. 작은 문제가 큰 문제의 부분 집합에 속해있다고 볼 수 있다. 기본적으로 다익스트라는 하나의 최단 거리를 구할 때 그 이전까지 구했던 최단 거리 정보를 그대로 사용한다는 특징이 있다. 

 

간단한 예제 문제 풀이로 이해해본다.

 

---

 

 

https://www.acmicpc.net/problem/5972

5972번: 택배 배송

문제

농부 현서는 농부 찬홍이에게 택배를 배달해줘야 합니다. 그리고 지금, 갈 준비를 하고 있습니다. 평화롭게 가려면 가는 길에 만나는 모든 소들에게 맛있는 여물을 줘야 합니다. 물론 현서는 구두쇠라서 최소한의 소들을 만나면서 지나가고 싶습니다.

농부 현서에게는 지도가 있습니다. N (1 <= N <= 50,000) 개의 헛간과, 소들의 길인 M (1 <= M <= 50,000) 개의 양방향 길이 그려져 있고, 각각의 길은 C_i (0 <= C_i <= 1,000) 마리의 소가 있습니다. 소들의 길은 두 개의 떨어진 헛간인 A_i 와 B_i (1 <= A_i <= N; 1 <= B_i <= N; A_i != B_i)를 잇습니다. 두 개의 헛간은 하나 이상의 길로 연결되어 있을 수도 있습니다. 농부 현서는 헛간 1에 있고 농부 찬홍이는 헛간 N에 있습니다.

다음 지도를 참고하세요.

           [2]---
          / |    \
         /1 |     \ 6
        /   |      \
     [1]   0|    --[3]
        \   |   /     \2
        4\  |  /4      [6]
          \ | /       /1
           [4]-----[5] 
                3  

농부 현서가 선택할 수 있는 최선의 통로는 1 -> 2 -> 4 -> 5 -> 6 입니다. 왜냐하면 여물의 총합이 1 + 0 + 3 + 1 = 5 이기 때문입니다.

농부 현서의 지도가 주어지고, 지나가는 길에 소를 만나면 줘야할 여물의 비용이 주어질 때 최소 여물은 얼마일까요? 농부 현서는 가는 길의 길이는 고려하지 않습니다.

---

 

이 문제 해결과정을 풀이해보면

[특정 정점 1에서 N이라는 정점을 향해 갈 때, 필요한 최소 비용 구하기]가 된다. 위에서 설명한 다익스트라 알고리즘의 정의가 그대로 적용된다. 따라서 다익스트라 알고리즘을 적용만 하면 해결이 되는 간단한 문제이다.

 

#include <bits/stdc++.h>
#define fastio ios::sync_with_stdio(false), cin.tie(0), cout.tie(0)
#define INF 123456789
#define endl '\n'

using namespace std;

typedef long long ll;

int N, M;
int distances[50000 + 1];
vector<pair<int, int>> adj[50000 + 1];

void input(){
	cin >> N >> M;
	for(int i=0;i<M;i++){
		int nodeA, nodeB, len;
		cin >> nodeA >> nodeB >> len;
		adj[nodeA].push_back({nodeB, len});
		adj[nodeB].push_back({nodeA, len});
	}
}

int solution(int start){
	memset(distances, INF, sizeof(distances));
	priority_queue<pair<int, int>> pq;

	pq.push({0, start});
	distances[start] = 0;

	while(!pq.empty()){
		int dist = -pq.top().first;
		int node = pq.top().second;
		pq.pop();

		
		if(distances[node] < dist) continue;

		for(int i=0;i<adj[node].size();i++){
			int cost = dist + adj[node][i].second;
			if(cost < distances[adj[node][i].first]){
				distances[adj[node][i].first] = cost;
				pq.push({-cost, adj[node][i].first});
			}
		}
	}

	return distances[N];
}

int main() {
	fastio;
	input();
	cout << solution(1) << endl;
	
	return 0;
}