Boj 1854 K번째 최단경로 찾기 c++

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

 

문제

단방향 그래프의 간선정보가 주어질 때, 1번 노드에서 각 노드까지의 최단경로 중에서 K번째 경로의 길이를 구하는 문제이다.

K번째 최단경로가 존재하지 않는 경우에는 -1을 출력한다.

 

접근 & 풀이

우선 다익스트라가 어떻게 작동하는지 되살펴볼 필요가 있다.

다익스트라에서 시작노드에서 n번 노드까지의 최단거리가 보장되는 핵심 로직이 무엇일까?

 

다익스트라는 시작노드와 도착 노드의 중간지점에 있는 노드까지의 최단거리가 항상 보장됨을 이용하여 최단거리를 확장해간다.

이는 최소힙의 성질 덕분이다. 특정 노드를 node라고 해보자.

현재 node가 최소힙에서 pop 되었다면 해당 거리는 주어진 그래프에서 1 -> node 경로 중에서 반드시 가장 짧은 경로임이 보장된다.

최소힙에서 pop되었다는 것은 다른 모든 노드들까지의 거리보다 짧다는 것이기 때문에, 양수가중치 그래프에서 더 짧은 경로로 node에 도달하는 방법은 존재하지 않는다.

 

일반적인 다익스트라에서는 두가지 조건

if(dist[curr] < cost)continue; // 해당 노드까지의 거리보다 더 긴 경로는 제외


if(dist[nx] > dist[curr] + ncost) {
	dist[nx] = dist[curr] + ncost;
    q.push({dist[nx], nx});
}

 

으로 특정 노드의 중복 방문을 방지한다. 해당 노드까지의 거리가 다른 모든 노드까지의 거리보다 짧은 경우에만 방문하며, 지속적으로 거리를 갱신하기 때문이다.

 

하지만 해당 문제에서는 노드의 중복 방문을 허용하여 K번째 최단경로를 구해야만 한다.

 

K번째 최단경로를 구하는 방법은 최단경로를 바라보는 시점에 따라서 2가지로 나뉠 수 있다.

 

방법1.

첫번째 방법은 가중치 합이 최소힙에 push 된 시점의 거리를 이용하여 최단거리를 추출하는 방식이다.

 

최대크기가 K인 Max Heap을 관리하는 방법이다.

각 정점까지의 K번째 최단경로는 말 그대로 1번노드에서 해당 정점까지 가는 경로 중에서 K번째로 짧은 경로이다.

즉, 해당 노드까지의 모든 경로 중에서 상위 K개의 거리만을 저장하면 된다.

 

때문에, node까지의 거리가 상위 K개 안에 들지 못하는 경우에는 push를 하지 않고 넘어간다. ---> 종료조건

 

첫번째 방법은 시간이 비교적으로 짧게 걸리고, 정석적인 방법이지만, 생각해내기가 어려운 풀이인 것 같다.

방법2. 

조금 더 직관적인 풀이이지만, 다익스트라의 원리를 정확하게 이해해야 떠올릴 수 있는 풀이이다.

우선 dist 배열의 정의를 dist[i][j] = i번 노드의 j번째 최단거리로 설정한다.

 

앞선 설명에서 다익스트라에서 curr 노드까지의 거리는 항상 최단거리임이 보장됨을 설명하였다.

그렇다면 중복 방문을 허용한 상태에서 최소힙에서 꺼내진 순서는 해당 노드까지의 최단거리 순서를 의미함을 알 수 있다.

 

노드 방문 횟수를 저장하고,  k번 이상의 방문을 제한하는 조건을 종료조건으로 사용하여 구현할 수 있다.

 

 

방법1코드

#include <bits/stdc++.h>
#define fastio ios_base :: sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
#define MAX 1000000001
using namespace std;
using pi = array<int, 2>;
int main() {
	fastio
	int n, m, k;
	cin >> n >> m >> k;
	vector<vector<pi>> connected(n+1);
	vector<priority_queue<int>> r(n+1);
	for(int i = 0; i < m; i++) {
		int u, v, d;
		cin >> u >> v >> d;
		connected[u].push_back({v, d});
	}
	priority_queue<pi, vector<pi>, greater<pi>> pq;
	pq.push({0, 1});
	r[1].push(0);
	while(!pq.empty()) {
		int curr, cost;
		curr = pq.top()[1];
		cost = pq.top()[0];
		pq.pop();
		for(auto x: connected[curr]) {
			int nx, ncost;
			nx = x[0];
			ncost = x[1];
			if(r[nx].size() < k) {
				r[nx].push(cost + ncost);
				pq.push({cost + ncost, nx});
			}
			else if(ncost + cost < r[nx].top()) {
				r[nx].pop();
				r[nx].push(ncost + cost);
				pq.push({cost + ncost, nx});
			}
		}
	}
	for(int i = 1; i <= n; i++) {
		if(r[i].size() < k) {
			cout << "-1\n";
			continue;
		}
		cout << r[i].top() << "\n";
	}
}

 

방법2코드

#include <bits/stdc++.h>
#define fastio ios_base :: sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
#define MAX 1000000001
using namespace std;
using pi = array<int, 2>;
int main() {
	fastio
	int n, m, k;
	cin >> n >> m >> k;
	vector<vector<pi>> connected(n+1);
	vector<vector<int>> dist(n+1, vector<int>(110, MAX));
	vector<int> cnt(n+1, 0);
	for(int i = 0; i < m; i++) {
		int u, v, d;
		cin >> u >> v >> d;
		connected[u].push_back({v, d});
	}
	priority_queue<pi, vector<pi>, greater<pi>> pq;
	pq.push({0, 1});
	for(int i = 1; i <= n; i++) {
		dist[i][0] = 0;
	}
	while(!pq.empty()) {
		int curr, cost;
		cost = pq.top()[0];
		curr = pq.top()[1];
		pq.pop();
		if(cnt[curr] > k)
			continue;
		dist[curr][++cnt[curr]] = cost;
		for(auto x : connected[curr]) {
			int nx, ncost;
			nx = x[0];
			ncost = x[1];
			pq.push({dist[curr][cnt[curr]] + ncost, nx});
		}
	}
	for(int i = 1; i <= n; i++) {
		if(dist[i][k] == MAX)
			cout << "-1\n";
		else
			cout << dist[i][k] << "\n";
	}
}

+

다익스트라에서 최단거리를 보장시켜주는 것은 조건문이 아니라 최소힙의 성질 자체임을 이해하게 해준 좋은 경험이었다.