[백준/C++] 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 이하의 자연수이다. 서로 다른 두 정점 사이에 여러 개의 간선이 존재할 수도 있음에 유의한다.

출력

첫째 줄부터 V개의 줄에 걸쳐, i번째 줄에 i번 정점으로의 최단 경로의 경로값을 출력한다. 시작점 자신은 0으로 출력하고, 경로가 존재하지 않는 경우에는 INF를 출력하면 된다.

예제 입력 1

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

예제 출력 1

0
2
3
7
INF

---

최단경로를 구하는 알고리즘에는 '다익스트라', '벨만포드', '플로이드 워셜' 등의 알고리즘이 존재한다.

이 문제는 음수의 가중치가 없는 그래프의 한 정점에서, 모든 정점까지의 최단거리를 구하는 문제이므로 '다익스트라' 알고리즘을 사용하였다.

 

다익스트라는 '배열' 또는 '우선순위 큐'를 이용해 구현할 수 있는데, 문제에서 주어진 정점의 최대 개수와 제한시간을 따져보면 배열로 풀었을 때 메모리 초과와 시간초과 문제가 발생한다.

 

(배열을 이용한 풀이는 아래 글에서 구현한 적이 있다.)

2023.05.15 - [💻코딩테스트/알고리즘, 자료구조] - [알고리즘] 다익스트라 (Dijkstra)

[알고리즘] 다익스트라 (Dijkstra)

 

따라서, 우선순위 큐를 사용하여 문제를 풀이했다.

 

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

#define INF 987654321

using namespace std;

int main()
{
	ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);

	int V, E, K;
	cin >> V >> E >> K;

	vector<pair<int, int>> graph[20001];
	vector<int> dist(20001);

	for(int i = 0; i < E; i++)
	{
		int u, v, w;
		cin >> u >> v >> w;
		graph[u].emplace_back(v, w); // 도착노드, 비용
	}
	fill(dist.begin(), dist.end(), INF);

	priority_queue<pair<int, int>, vector<pair<int, int>>, greater<>> pq; // 비용, 도착노드			
	pq.push({ 0, K });
	dist[K] = 0;

	while (!pq.empty())
	{
		int cost = pq.top().first;				// 현재 노드까지의 비용
		int cur = pq.top().second;				// 현재 노드
		pq.pop();

		for (int i = 0; i < graph[cur].size(); i++)
		{
			int next = graph[cur][i].first;		// 다음 노드
			int nCost = graph[cur][i].second;	// 다음 노드까지의 비용

			if(dist[next] > cost + nCost)
			{
				dist[next] = cost + nCost;
				pq.push({ dist[next], next });
			}
		}
	}

	for(int i = 1; i <= V; i++)
	{
		if (dist[i] == INF)
			cout << "INF\n";
		else
			cout << dist[i] << "\n";
	}
	return 0;
}

 

풀이를 차례로 보면, 입력 값으로 받는 노드와 비용 정보를 담은 graph 배열 말고도, 최단 거리를 저장할 dist 배열이 추가로 존재한다.

 

dist 배열은 무한대 값으로 초기화한 뒤 시작한다.

 

우선순위큐 pq를 greater<>인 오름차순 정렬하도록 선언하여 최소힙으로 만들었다.

우선순위 큐에 pair<int, int> 쌍을 넣는데 첫번째 원소로 노드 간 비용을, 두번째 원소로 노드를 저장하여 거리가 가장 작은 노드부터 꺼내 사용할 수 있도록 구현하였다.

 

차례로 연결된 노드에 존재하는 모든 원소를 for문(i = 0 -> i < graph[cur].size()) 로 검사하며 현재의 거리 값보다 더 작은 거리 값으로 갱신될 수 있는지 조건문을 검사했다.

현재 비용(cost)에 다음 노드까지의 비용(nCost)를 더한 거리 값이 더 작은 경우 거리 배열을 갱신해주었다.

 

이렇게 모든 노드 사이의 최단 경로를 저장한 dist 배열을 차례로 출력하면 문제풀이가 마무리된다.

 

💥 주의

참고로, 우선순위 큐에서 {비용, 노드} 순서가 아닌 {노드, 비용} 순서로 값을 저장하면
cost를 찾아 계산하는 과정에서 첫번째 원소인 '노드'가 먼저 비교 연산되므로 시간초과가 발생한다!!

---

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

1753번: 최단경로