백준 1854번 K번째 최단경로 찾기 문제 풀이

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

1854번: K번째 최단경로 찾기

 

방금 작성한 포스팅이 1753번 최단경로 문제(다익스트라 기본문제) 였는데, 이 포스팅을 쓰면서 오랜만에 다익스트라 알고리즘을 다시 한번 생각해보게 되었었다.

 

근데 곧이어 1854번 문제를 풀었는데 그냥 생각나는대로 푸니 되었어서 좀 얼떨떨한 상태이다.

 

어쨋든 방금 서술한 것과 마찬가지로 1854번 문제도 다익스트라 최단경로 찾기 알고리즘을 사용하는 문제인데, 기본적인 다익스트라 알고리즘은 shortest path므로 가장 짧은 경로를 찾는 알고리즘이다.

 

그런데 이 문제를 보면 K번째로 짧은 경로를 찾아야 한다.

 

그래서 아까 포스팅에서 다익스트라 알고리즘을 이야기 하다가 나왔는데, 우선순위 큐에서 가장 먼저 나와서 해당 정점을 처음 방문한 녀석이 가장 짧은 길이라고 서술했었다.

그리고 큐에는 그 정점을 방문할 만한 다른 path 결과도 있지만 처음 나온 녀석이 가장 짧은 경로이기 때문에 그리디 알고리즘이라고도 이야기를 했었다.

 

그렇다면 두번째로 그 정점을 방문한 녀석은 두번째로 짧은 경로가 될 것이고, 세번째로 방문한 녀석은 세번째로 짧은 경로가 될 것이다.

 

이러한 방식으로 K번째 방문한 path로 길이를 설정하면 K번째 최단경로를 구할 수 있을 것이다.

 

다행히 K값이 100으로 작고 N도 1000로 정점수가 그에 맞게 작은 값이다.

 

이를 이용하여 다익스트라 알고리즘을 변형하면 문제를 쉽게 풀 수 있다.

 

코드

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;

#define INF 2000000000
#define MAXN 1003
#define MAXK 102
vector<pii> edges[MAXN]; //dest, weight
int visit[MAXN];
int dist[MAXK][MAXN]; // [i][j] = i번째 최단경로로 j방문하는 길이
int main() {
	int discovered = 0;
	int n, m, k;
	scanf("%d%d%d", &n, &m, &k);
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= k; j++) {
			dist[j][i] = INF;
		}
	}
	for (int i = 0; i < m; i++) {
		int u, v, w;
		(void)scanf("%d%d%d", &u, &v, &w);
		edges[u].push_back({ v, w });
	}
	priority_queue<pii> pq; // -dist, index
	pq.push({ 0, 1 });
	while (pq.size()) {
		pii cur = pq.top(); pq.pop();
		int distance = -cur.first;
		int current = cur.second;
		if (visit[current] >= k) continue; //k번째 최단경로를 다 구한경우
		int cnt = ++visit[current]; //방문 횟수
		dist[cnt][current] = distance;
		if (cnt == k) discovered++;
		if (discovered == n) break;
		for (pii nx : edges[current]) {
			int next = nx.first;
			int weight = nx.second;
			pq.push({ -dist[cnt][current] - weight, next });
		}
	}
	for (int i = 1; i <= n; i++) {
		if (dist[k][i] == INF) {
			puts("-1");
		}
		else {
			printf("%d\n", dist[k][i]);
		}
	}
	return 0;
}