[백준 1854] K번째 최단경로 찾기 (C++)

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

문제

유향 그래프가 주어집니다. 여기서 1번에서 1 ~ N 까지의 K번째 최단경로를 1줄 씩 출력하면 되는 문제 입니다. 이해하기 쉽고 간단한 지문이지만 여기서 주의해야 할 점이 몇 가지 있습니다.

1번에서 1번까지 가는 가장 짧은 거리는 0이다.

지문에서는 "i번 도시에서 i번 도시로 가는 최단경로는 0이지만" 이라고 적혀 있습니다.즉 1번에서 1번으로 가는 간선이 없더라도 1번에서 1번까지 가는 최단 경로는 무조건 0 입니다. 그렇기 때문에 1 -> 1로 가는 간선이 없을 때, K가 2 이상이면 -1이 답이겠지만 K=1면 0이 답이 됩니다.

같은 값의 경로가 여러개 주어졌어도 하나로 합치지 않고 그대로 나열한다.

예를 들어 1등 최단거리부터 5등 까지가 [1,2,3,3,3]이라고 주어졌고 4가 들어올 때, 3이 3개 있고 얘들은 3등이니까 4는 4등이 되는 것이 아니라 [3, 3, 3]은 곧 [3등, 4등, 5등]으로 표현되기 때문에 4는 3등이 아닌 6등이 됩니다.

풀이

전형적인 데이크스트라(다익스트라)를 이용한 풀이 입니다. 하지만 데이크스트라에 사용되는 자료구조와 알고리즘을 개조해야 합니다.

보통 데이크스트라를 돌린다고 한다면 정점 길이의 배열에 각 정점의 최단 거리를 저장해서 진행을 하는 방식으로 구현해 왔지만. 몇 번 째 최단경로를 구해야 하기 때문에 각 정점에 대해 변수가 아닌 자료구조가 들어가야 합니다.

자료구조가 배열이라고 가정할 때, 배열 안의 요소의 갯수가 K개 이하라면 들어오는 경로 값이 K번째 이하이기 때문에 그냥 배열 안에 추가하면 되지만, K개가 되었을 때, 해당 배열안의 요소 중 가장 큰 값과 새로 들어오는 값을 비교해서 새로운 경로 값을 배열 안에 집어 넣을 지 결정해야 합니다. 즉 배열 안의 가장 큰 값이 새로운 경로 값 보다 크다면 새로운 경로 값이 K번 째 이하의 경로값이 되고 반대로 기존의 가장 큰 값이 K+1번째 경로가 되므로 서로 교체하면 됩니다. 이러한 작업을 하려면 정렬을 해야 하는데, 이는 시간이 오래 걸리는 작업 (O(NlogN))이므로 배열이 아닌 우선순의 큐를 사용합니다. (O(logN))

이런 식으로 모든 경로를 구하고 난 다음, 1번 정점 부터 차례대로 우선순위의 큐의 요소 갯수가 K개면 가장 맨 앞의 값을 꺼내 출력하고 그 이하면 K번째 경로가 없다는 의미이므로 -1을 출력하면 됩니다.

정리

데이크스트라에서의 최단경로 값을 저장하는 자료구조를 변수가 아닌 우선순위 큐로 선언
우선순위 큐에 있는 경로값의 갯수가 K이하라면 그냥 집어넣고 K면 우선순위 큐에서 가장 큰 값을 꺼내 새로운 경로 값과 비교해서 새로운 경로 값이 작으면, 기존의 가장 큰 값을 꺼내고 새로운 경로 값을 집어넣고, 그렇지 않으면 그냥 새로운 경로 값을 버린다.

코드 보기 (C++)

#include <iostream>
#include <queue>

using namespace std;

int main(void)
{

	ios_base::sync_with_stdio(false);
	cin.tie(nullptr); cout.tie(nullptr);

	int N, M, K;
	vector<pair<int, int>> g[1001];
	queue<pair<int, int>> q;
	priority_queue<int> weights[1001];

	cin >> N >> M >> K;
	for(int i = 0; i < M; i++) {
		int u, v, w;
		cin >> u >> v >> w;
		g[u].push_back({v, w});
	}
	q.push({1, 0});
	
	// 1 -> 1의 최단경로는 9이다.
	weights[1].push(0);

	while(!q.empty()) {
		int u = q.front().first, w = q.front().second;
		q.pop();
		for(int k = 0; k < (int)g[u].size(); k++) {
			int v = g[u][k].first, next_w = g[u][k].second + w;
			if(weights[v].size() < K || weights[v].top() > next_w) {
				// 우선순위의 배열 갯수가 K이하이거나 가장 큰 값이 새 경로보다 더 큰 경우
				// 교체
				if(weights[v].size() == K) weights[v].pop();
				weights[v].push(next_w);
				q.push({v, next_w});
			}
		}
	}
	for(int u = 1; u <= N; u++) {
		if(weights[u].size() < K) cout << -1 << '\n';
		else cout << weights[u].top() << '\n';
	}
	return 0;
}

이왜플?

플래티넘4 치고는 개인적으로 아이디어 자체가 어렵지 않았습니다. 경로를 저장하는 자료구조만 우선순위 큐로 바꾸면 그만이니까요. 혹시나 이거 말고 다른 방법으로 푼게 있나 하고 블로그도 뒤져보고 다른사람이 짠 코드도 보고 그랬는데 대부분 이 방식하고 비슷한 방식인 것 같네요. 그래서 썸네일도 녹색테두리가 아닌 금테입니다. 개인적으로 체감 난이도가 골드2정도 되는 것 같네요