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

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

 

나는 솔브닥 티어를 "성공인 경우만 보기"로 설정을 해서, 내가 푸는 문제의 티어를 보지 않도록 설정하였다.

그런데, 이 문제는 평소와 달리 문제를 처음 봤을 때, 답이 안 떠올라서 솔브닥 티어를 보았다. 그 때, 이 문제가 플레티넘 4란 비교적 높은 티어를 배정 받아서, 내가 풀기엔 힘든 문제라고 단정짓고 다른 문제를 해결했던 기억이 있다. 플레티넘 4 이상의 문제를 자력으로 해결한 경험이 없는 건 아니지만 하나 같이 만만한 문제가 아니여서 넘어갔던 것 같다.

 

그렇게 시간이 지나고, 해결할 문제를 찾던 도중 이 문제를 다시 마주하게 되었다. 이번엔 맞힌 사람이 많은 것을 보고, 내가 해결할 수 있을것이라 가정을 하고 문제에 임하였다.

 

문제를 처음 봤을 떄의 떠올린 해결책은 매우 심플했다. 다익스트라 알고리즘을 돌다가 K번째로 해당 위치를 방문하면 그것이 정답일 것이다란 가정이였다. 하지만, K번째로 방문을 한다해도, 그것이 K번째 최단경로임이 보장이 안 되어있다는 것을 깨달았다. 여기까지 생각을 하고 문제 해결을 포기했었지만, 이번엔 해결을 할 수 있다는 자신감을 가지고 문제 해결책을 강구하였다.

 

문득, K번째 방문이 K번째 최단경로임이 보장이 안 되어있다면, 기존의 다익스트라에서 시작점에서 다른 점까지의 최단경로를 저장하는 배열로는 문제해결이 어렵다고 생각을 하였다. 이 배열은 최단경로의 소요시간만을 저장하는데, 2 이상의 K번째 최단경로를 구하는데, 전혀 도움이 안된다고 판단을 했다. 그럼 변형을 해서 사용을 할 수 없을까? 란 생각에 이르렀고, 지금까지의 최단경로의 소요시간을 배열에 저장하면 어떨까?란 가정을 했을 때, 좋은 해결책이 떠올랐다.

 

다익스트라를 돌리되, 소요시간을 우선순위 큐에 저장하는 것이다.

기존의 다익스트라는 최단경로의 소요시간을 숫자 배열에 저장해서 우선순위 큐를 돌며 큐에 저장된 값과 소요시간을 비교해서 소요시간을 갱신하는 방식이였다. 하지만 이번 문제에선 숫자 배열 대신 최대 값 우선순위 큐를 사용해서(이하 시간 큐), 해당 위치를 방문했을 때, 해당 위치의 시간 큐의 사이즈가 K보다 작으면 시간 큐에 값을 넣고, K와 동일하면 시간 큐에 가장 위에 있는 값과 비교해서 그 값보다 현재의 거리 값이 크면 현재 값을 파기, 작으면 시간 큐를 pop하고, 현재 거리를 넣는 방식이다.

 

시작위치의 시작큐에 0을 넣어서 시작위치를 1번째 최단경로를 0으로 만들어야한다는 점을 유의하자.

#include <iostream>
#include <queue>
#include <algorithm>
#include <cstring>
using namespace std;
const int INF = 1000000007;
vector<pair<int, int>> adj[1001];

priority_queue<pair<int, int>> pq;
priority_queue<int> D[1001];
int N, M, K;
int A, B, C;

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL); cout.tie(NULL);
	cin >> N >> M >> K;
	for(int i = 0; i < M; i++)
	{ 
		cin >> A >> B >> C;
		adj[A].push_back({ B, C });
	}
	pq.push({ 0, 1 });
	D[1].push(0);
	while (!pq.empty())
	{
		int here = pq.top().second;
		int cost = -pq.top().first;
		pq.pop();
		for (int i = 0; i < adj[here].size(); i++)
		{
			int there = adj[here][i].first;
			int nxtCost = adj[here][i].second + cost;
			if (D[there].size() < K) D[there].push(nxtCost);
			else
			{
				if (D[there].top() <= nxtCost) continue;
				D[there].pop();
				D[there].push(nxtCost);
			}
			pq.push({-nxtCost, there});
		}
	}
	for (int i = 1; i <= N; i++)
		if (D[i].size() < K) cout << -1 << '\n';
		else cout << D[i].top() << '\n';
}

이렇게하면 아이디어가 필요하지만, 그렇게 어려운 문제가 아닌데, 괜히 난이도를 신경써서 문제를 회피해왔던 것 같다. 다음부터는 좀 더 자신감을 가지고, 문제해결에 임해보자.