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

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

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

---

Solved By: Dijkstra, Priority Queue

 

Reference: (https://justicehui.github.io/ps/2019/04/10/BOJ1854/)

• 각 노드에 대하여 최단 경로를 구하여야 하는데 cost의 값 범위가 음수가 되지 않으므로 Dijkstra를 이용하여도 됩니다.

모든 노드에 대해 Dijkstra를 돌려 각 노드에 대해 N번째 최단 경로 값을 저장할 생각이었지만 이러면 총 시간 복잡도가 O(V * ElogV)가 되므로 이는 Time Limited를 발생시킵니다.

V = 총 노드의 개수

ElogV = 다익스트라의 시간 복잡도

 

참고한 자료에서는 Priority Queue를 활용한 풀이를 제공합니다.

Priority Queue를 활용하여 Array형태의 Priority Queue를 하나 선언합니다. (Priority Queue는 Heap의 형태이기 때문에 heap이라는 이름으로 선언합니다.)

 

Array의 형태로 Priority Queue를 선언한 이유는 각 노드에 대해 각 노드에 대해 K개의 최단 경로 값을 저장하기 위해서입니다. 그래서 N개의 Priority Queue가 필요하지만 이를 Array의 형태로 선언한 것입니다.

 

[Solution]

• 해당 Priority Queue(heap)를 활용하여 Dijkstra가 진행되는 과정에서 next 노드까지의 거리값(nextCost)이 next의 heap 사이즈가 현재 K개보다 작다면 Heap에 우선적으로 넣습니다. -> K개의 최단 경로는 우선적으로 채워야 하기 때문입니다.
• 하지만, 그렇지 않은 경우 next의 heap.top()이 nextCost보다 큰 값을 가지는지 확인합니다. 선언된 heap은 maxHeap 기본적으로 Max Heap 구조라서 최댓값이 top으로 올라와있기 때문입니다. 우리는 최단 경로 값을 구하고 있기 때문에 nextCost가 더 작다면 현재의 top을 pop 처리하고, 해당 nextCost를 heap에 넣어서 새로운 최단 경로 값을 가져옵니다.
• 시작 노드는 1에서 시작하기 때문에 1에 대한 heap에는 0을 push 하고 시작합니다. (1에서 1로 가는 최단 경로는 0이기 때문)

나머지는 Dijkstra의 메커니즘 그대로 가져가면 됩니다.

 

이렇게 되면 모든 노드에 대한 Dijkstra를 돌릴 필요도 없고, 이로 인해 전체적인 시간 복잡도를 Dijkstra 한 번으로 줄일 수 있습니다.

 

[핵심 아이디어 정리]

즉, Dijkstra를 기존에는 dist 배열을 선언하여 계속 노드에 대한 최솟값으로 할당을 했습니다.

이번 문제에서는 다른 방식으로 응용하여 최솟값을 할당을 하지 않고, 각 노드마다 K개의 최솟값을 가지고 있게 해야 합니다.

그러한 이유에서 '배열의 각 노드에 대한 최솟값 할당 -> Priority Queue의 각 노드에 대한 최솟값 push'로 이번 문제의 핵심 아이디어를 요약할 수 있겠습니다.

 

그리고, main 코드에서 각 노드를 탐색하며 각 노드에 대한 heap의 사이즈가 k개를 넘게 하지 않았으므로 사이즈가 k개가 아니라면 K번째 최단 경로가 없다는 것을 의미하는 -1을 출력합니다.

 

그렇지 않은 경우는 top값을 출력하여 K번째 최단 경로 값을 알려줍니다.

#include <iostream>
#include <vector>
#include <queue>
#define MAX 1001
#define pii pair<int, int>
using namespace std;

vector<pii> adj[MAX];
priority_queue<int> heap[MAX];
int n, m, k;

struct cmp{
    bool operator()(pii &a, pii &b){
        return a.second > b.second;
    }
};

void dijkstra(){
    priority_queue<pii, vector<pii>, cmp> pq;
    pq.push({1, 0});
    heap[1].push(0);
    
    while(!pq.empty()){
        int now = pq.top().first;
        int nowCost = pq.top().second;
        pq.pop();
        
        for(int i = 0; i < adj[now].size(); i++){
            int next = adj[now][i].first;
            int nextCost = nowCost + adj[now][i].second;
            
            if(heap[next].size() < k){
                heap[next].push(nextCost);
                pq.push({next, nextCost});
            }
            else if(heap[next].top() > nextCost){
                heap[next].pop();
                heap[next].push(nextCost);
                pq.push({next, nextCost});
            }
        }
    }
}

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    
    cin >> n >> m >> k;
    for(int i = 0; i < m; i++){
        int v, u, w; cin >> v >> u >> w;
        adj[v].push_back({u, w});
    }
    
    dijkstra();
    
    for(int i = 1; i <= n; i++){
        if(heap[i].size() != k) cout << -1;
        else cout << heap[i].top();
        cout << '\n';
    }
    
    return 0;
}