[백준 / C++] 1753 번 최단경로 구하기 - (1) , 다익스트라, 우선순위 큐

백준 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

 

---

문제 분석

 

이 문제는 최단거리를 구하는 문제이지만, 최단거리 ? -> BFS 랑은 다르게 거리의 가중치가 존재하기 때문에 일반적인 BFS로는 풀 순 없다. 가중치 문제에 BFS를 적용하면 일반적으로 내가 이미 확인한 부분은 넘어가는 BFS는 적용하지 못하여, 확인한 부분은 또 확인해야하기 때문에 시간 복잡도가 O(V * N)이 넘어간다. ( 똑같은 부분에서 뒤에 확인하는 부분이 가중치가 더 낮질 수 있기 때문에)

 

따라서, 가중치가 양의 수이고 최단거리를 구해야한다면 다익스트라 알고리즘을 적용하는 것이 낫다. 

다익스트라 알고리즘 중 우선순위 큐를 적용하면 시간복잡도 O(NlongN)으로 구할 수 있다. 

 

우선순위 큐를 적용하는 방법은 2가지를 쓸 수 있다.

1. 오름차순 우선순위 큐

2. 내림차순 우선순위 큐

 

일반적으로 우선순위 큐를 적용하면, 오름차순 큐이다. (아래 코드)

priority_queue<pair<int, int>> que;

 

내림차순 큐는 아래 코드와 같이 작성해야한다. (조금 번거롭다.)

priority_queue<pair<int,int>, vector<pair<int,int>>, greater<pair<int,int>> > pq;

 

따라서, 많은 사람들이 1번 처럼 쓰되, 대신 값을 집어넣을 때 앞에 - (마이너스)를 붙여서 사용하여 내림차순 처럼 사용한다.

나 또한 이번 코드에서는 값에 -를 붙여서 사용했다.

while (!que.empty()) {
	int u = que.top().second;
	int past_w = -que.top().first;
	que.pop();

	if (d[u] < past_w) continue;

	for (int j = 0; j < dis[u].size(); j++) {
		int v, w;
		v = dis[u][j].first;
		w = dis[u][j].second;


		if (d[v] > d[u] + w) {
			d[v] = d[u] + w;
			que.push({ -d[v], v });
		}

}

최단 거리 전체 코드

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

using namespace std;

int V, E;
bool check[20001];

vector<pair<int, int>> dis[20001];
int INF = 0x3f3f3f3f;
int d[20001];

int main() {
	cin.tie(0);
	ios::sync_with_stdio(0);
	cin >> V >> E;

	int k;
	cin >> k;
	fill(d, d + V + 1, INF);

	for (int i = 0; i < E; i++) {
		int u, v, w;
		cin >> u >> v >> w;

		dis[u].push_back({ v,w });
	}

	priority_queue<pair<int, int>> que;
	que.push({ 0, k });
	d[k] = 0;
	while (!que.empty()) {
		int u = que.top().second;
		int past_w = -que.top().first;
		que.pop();

		if (d[u] < past_w) continue;

		for (int j = 0; j < dis[u].size(); j++) {
			int v, w;
			v = dis[u][j].first;
			w = dis[u][j].second;


			if (d[v] > d[u] + w) {
				d[v] = d[u] + w;
				que.push({ -d[v], v });
			}

		}

	}

	for (int i = 1; i <= V; i++) {
		if (d[i] == 1061109567) {
			cout << "INF" << '\n';
			continue;
		}
		cout << d[i] << '\n';
	}

	return 0;
}