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

문제 : K번째 최단경로 찾기

유형 : 다익스트라

---

문제 해석

• 1번 도시에서 i번 도시로 가는 k번째 최단경로의 소요시간을 출력한다.
  • 도시의 번호는 1번부터 n번까지 연속하여 붙어 있으며, 1번 도시는 시작도시이다.
  • k번째 최단경로가 존재하지 않으면 -1을 출력한다.
  • 최단경로에 같은 정점이 여러 번 포함되어도 된다.

해결 전략

• 다익스트라를 응용한다.
  • 순수 다익스트라를 이용하면 항상 1번째 최단경로를 알 수 있다.
  • 따라서 다익스트라 최단경로 코드 에서 if(now_cost > dist[now_node]) continue; 를 제거해 주고 각 정점마다 최소 k 번 이상 방문하게 해야 한다. 각 정점이 만약 K 번 방문하지 못한다면 K 번째 간선은 없다.
  • 만약에 K 번 이상 방문했더라도, 먼저 정점을 방문했다고 소요시간이 적다는 보장이 없다.
    하지만 각 정점에 연결되는 간선들이 소요시간이 적은 순서대로 연결돼있다면? 먼저 정점을 방문하면 무조건 소요시간이 적다. 즉 각 정점에 K 번 방문하는 순간 그 경로가 K 번째 걸리는 소요 시간이다.

설계, 구현

• 해결 전략에서 말한것과 같이 그대로 구현하면 된다.

• 각 정점마다 K 번 이상 방문하게 한다.

priority_queue<int, vector<int>, less<int>> city[1001];

if(city[next_node].size() < k) {
	city[next_node].push(next_cost);
	pq.push({next_cost, next_node});
}

• 만약 K 번 이상 방문한다면, 가장 큰 값을 없애고 새로운 값을 추가해 k 번째 값으로 만든다.

else {
	if(city[next_node].top() > next_cost) {
		city[next_node].pop();
		city[next_node].push(next_cost);
		pq.push({next_cost, next_node});
	}
}

---

주의할 점

근데 위와 같이 코드를 짜면 시간 복잡도가 얼마나 될까? 계산해 보자.

정점의 최대 개수 (V) : 1000 (1천)
간선의 최대 개수 (E) : 2000000 (2백만)
도시의 최대 개수 (K): 100 (1백)

일반적인 다익스트라의 시간복잡도는 O(ElogE)다. 그래서 k개의 도시를 도니깐 O(k * ElogE)일까? 이 문제는 일반적인 다익스트라의 코드를 변경 했으므로 시간복잡도에 주의하자.

오히려 if(now_cost > dist[now_node]) continue; 부분을 제거해서 최악의 경우 O(E^2 / 2)인데? 그럼 O(2백만^2 / 2) 무려 1조다.

근데 잘 생각해보자 우리는 각 정점에 연결되는 간선들의 소요시간이 오름차순으로 정렬되어 있기때문에 한 정점에서 다른 정점을 가는데 걸리는 최대 소요시간은 1000시간이다. 그럼 최악의 경우에 한 정점에서 다른 정점으로 가는데 간선이 2백만개씩 있더라도 1000개의 간선만 거치면 최소 소요시간을 알 수 있다.

그래서 시간복잡도는 O(V * 1000 * K)다.
최악의 경우 1000 * 1000 * 100 으로 O(1억)이다.

---

코드

#include <bits/stdc++.h>
#define INF 1e9
using namespace std;

int V, E, k, start = 1;
vector<pair<int, int> > graph[1001];
priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
priority_queue<int, vector<int>, less<int>> city[1001];

void input() {
	cin >> V >> E >> k; // n, m, k
	
	int u, v, w;
	for(int i=0; i<E; i++) {
		cin >> u >> v >> w;
		graph[u].push_back({w, v});
	}
}

void dijkstra() {
	pq.push({0, start});
	city[start].push(0);
	
	while(!pq.empty()) {
		int now_cost = pq.top().first;
		int now_node = pq.top().second;
		pq.pop();
		
		for(int i=0; i<graph[now_node].size(); i++) {
			int next_cost = now_cost + graph[now_node][i].first;
			int next_node = graph[now_node][i].second;
			 
			if(city[next_node].size() < k) {
				city[next_node].push(next_cost);
				pq.push({next_cost, next_node});
			} else {
				if(city[next_node].top() > next_cost) {
					city[next_node].pop();
					city[next_node].push(next_cost);
					pq.push({next_cost, next_node});
				}
			}
		}
	}
	
}

int main() {
   	ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    
	input();
	dijkstra();
	
	// output
	for(int i=1; i<=V; i++) {
		if(city[i].size() < k) cout << -1 << endl;
		else {
			cout << city[i].top() << endl;
		}
	}
	return 0;
}