C++ / 1735 / 최단경로 ( 다익스트라 )

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

문제 요약

방향그래프가 주어지면 주어진 시작점에서 다른 모든 정점으로의 최단 경로를 구하는 프로그램을 작성해야합니다. 단, 모든 간선의 가중치는 10 이하의 자연수입니다.

 

첫째 줄에 정점의 개수 V와 간선의 개수 E가 주어집니다. (1 ≤ V ≤ 20,000, 1 ≤ E ≤ 300,000) 모든 정점에는 1부터 V까지 번호가 매겨져 있다고 가정합니다. 둘째 줄에는 시작 정점의 번호 K(1 ≤ K ≤ V)가 주어집니다. 셋째 줄부터 E개의 줄에 걸쳐 각 간선을 나타내는 세 개의 정수 (u, v, w)가 순서대로 주어집니다. 이는 u에서 v로 가는 가중치 w인 간선이 존재한다는 뜻이다. u와 v는 서로 다르며 w는 10 이하의 자연수입니다. 서로 다른 두 정점 사이에 여러 개의 간선이 존재할 수도 있음에 유의합니다.

문제 풀이

갑자기 코딩테스트 일정이 생겨 급하게 다익스트라 알고리즘을 공부하였습니다.
다익스트라를 한문장으로 요약하면
최단경로 ( 최소코스트 ) 를 구해서 저장해두는 알고리즘이라고 할 수 있습니다.
bfs와 비슷하게 탐색하지만 각 간선별로 다른 가중치 ( 코스트, 자연수일 경우 )를 가지고 있고 그 가중치가 최소한이 되는 경우를 저장합니다. 


1. 그래프를 입력받기 위한 백터를 만듭니다. 백터는 3차원입니다. v[현재 노드].push_back({ 다음 노드, 다음 노드 코스트 })

2. dist 배열을 만듭니다. 이 배열은 각 노드별로 최소 비용을 저장해둡니다. ( 방문 처리 )

3. 그래프를 입력받고 dist 배열을 초기화합니다.

4. 다익스트라 알고리즘을 실행합니다. 첫줄에는 오름차순으로 저장 되는 프리오리티 큐를 만들고 시작 노드의 코스트와 시작 노드를 푸시합니다.

5. dist배열에 현재 노드의 코스트를 저장합니다. ( 시작 노드기 때문에 0 )

6. while문을 돌리는데 만들어둔 프리오리티 큐에서 현재 코스트와 현재 노드를 저장하고  pop합니다. 

7. 현재 노드의 코스트가 이미 확인된 (1e9가 아닌 더 작은 갱신된 값 ) 경우라면 스킵합니다. 혹은 현재 갱신할려는 값이 더 크면 스킵합니다.

8. 현재 노드 기준으로 연결되어 있는 노드들을 for each으로 탐색합니다.

9. 다음 노드와 다음 노드 까지의 코스트( 다음 노드의 코스트  + 현재 까지 코스트 )를 저장합니다.

10. dist 배열에 다음 노드의 코스트가 방금 계산한 다음 노드까지의 코스트보다 클경우 갱신해줍니다.

11. 그다음 pq에 다음 코스트와 다음 노드를 추가하여 다음 탐색을 해줍니다.

12. 다익스트라 알고리즘을 마치고 메인으로 돌아와 각 노드별로 코스트를 출력합니다.  

주의할 점

단방향 그래프 인점을 주의해야 합니다.

코드

#include<iostream>
#include<vector>
#include<algorithm>
#include<queue>

using namespace std;

int n, m, start;

vector<pair<int, int>>v[300004];
// 최단 경로 코스트 저장할 배열
int dist[20004];

void dijkstra(int start)
{
	// 오른차순 pq
	priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>>pq;
	pq.push({ 0, start });
	dist[start] = 0;
	while (!pq.empty())
	{
		// 현재 코스트
		int cost = pq.top().first;
		// 현재 노드
		int now = pq.top().second;
		pq.pop();

		// 현재 노드 코스트가 이미 확인된 (1e9가 아닌 혹은 더 작은 값을 가진) 경우라면 패스
		if (dist[now] < cost)
		{
			continue;
		}
		// 현재 노드와 연결된 노드 탐색
		for (auto i : v[now])
		{
			// 다음 노드
			int nextNode = i.first;
			// 다음 코스트 = 현재 코스트와 다음 코스트의 합
			int nextCost = i.second + cost;

			// 다음 노드의 코스트가 저장되어있는 코스트 보다 작으면 갱신
			if (dist[nextNode] > nextCost)
			{
				// 갱신
				dist[nextNode] = nextCost;
				// 다음 탐색
				pq.push({ nextCost, nextNode });
			}
		}
	}
}

int main()
{
	cin >> n >> m >> start;

	for (int i = 0; i < m; i++)
	{
		int a, b, c;
		cin >> a >> b >> c;
		// 단방향 그래프
		v[a].push_back({ b, c });
	}
	// 초기값
	fill(dist, dist + n + 1, 1e9);
	// 다익스트라
	dijkstra(start);

	// 경로별로 코스트 출력
	for (int i = 1; i <= n; i++)
	{
		if (dist[i] == 1e9)
		{
			cout << "INF" << "\n";
		}
		else
		{
			cout << dist[i] << "\n";
		}
	}
	return 0;
}

예제

5 6
1
5 1 1
1 2 2
1 3 3
2 3 4
2 4 5
3 4 6

결과