1854번: K번째 최단경로 찾기 - Baekjoon Online Judge

K번째 최단경로 찾기는 최단경로 알고리즘 중에서 가장 기본적이고, 가장 널리 알려진 다익스트라(Dijkstra) 알고리즘의 응용 문제이다. 다익스트라 알고리즘에 대해 간단히 알아보자면 다익스트라 알고리즘은 노드와 간선으로 이루어진 그래프가 있을 때, 하나의 노드를 출발점으로 하여 목표 노드까지 도달하는데 드는 비용을 최소화시키는 알고리즘이다. 알고리즘이 갖는 의미가 비교적 단순명료하여 이해하기는 쉬운데 처음 소스로 구현하자면 어떻게 해야할지 방향 잡기가 힘들다. 간단히 다익스트라 알고리즘 푸는 법을 설명하자면, 처음 시작점에서부터 갈 수 있는 노드들을 탐색하여, 해당 노드까지 가는데 드는 비용이 최소가 되도록 업데이트 해준다. 그리고 비용을 줄여서 이동 가능한 노드들이 우리가 도착 목표로 하고 있는 노드에 최소 비용으로 도착하는데 중간 경유지가 될 것이라는 가정하에 노드 정보를 Queue에 저장해주면서 반복적으로 탐색해준다. 결국 모든 노드에서 모든 간선에 대한 탐색이 끝나게 되면 출발점에서 각 노드에 도착할 수 있는 가장 낮은 비용만이 남게 되고 답을 구할 수 있게 된다. 말로만 해서는 이해하기 어려울 듯하여 나무위키 link를 남겨놓았다.

다익스트라 알고리즘

https://namu.wiki/w/%EB%8B%A4%EC%9D%B5%EC%8A%A4%ED%8A%B8%EB%9D%BC%20%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98

K번째 최단경로 찾기 문제는 일반적인 다익스트라 알고리즘 문제와는 다르게 노드에 도착하는데 드는 최소의 비용이 아닌 최소비용으로부터 K번째에 있는 비용을 구하는 문제이다. 문제에서 요구하는 답이 최소비용에서부터 K번째에 해당하는 값인만큼 일반적인 풀이와 다르게 각 노드마다 저장되는 비용정보는 최소비용 하나에서 그치는 것이 아니라 적어도 K개는 저장이 되어있어야 한다는 것을 알 수 있다. 물론 노드에 도착할 수 있는 간선의 가짓 수에 따라서 도달할 수 있는 방법의 수도 결정되기 때문에 K개에 도달할 수 없을 수 있지만, 그러한 경우는 -1을 출력하도록 문제에서 조건을 두었다. 그리고 노드에 도달할 수 있는 방법의 수가 K개를 넘어서 존재한다면 최소비용 중에서 K개만 골라서 저장해줘도 문제의 답을 구하는데 전혀 지장이 없다는 사실도 알 수 있다. 

Baekjoon Algorithm Judge 1854번 문제로 풀어볼 수 있다.

1854번: K번째 최단경로 찾기 - Baekjoon Online Judge

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

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Comparator;
import java.util.PriorityQueue;
import java.util.StringTokenizer;
 
public class Main {
    private static int n;
    private static ArrayList<Integer>[] con;
    private static ArrayList<Integer>[] conv;
    private static PriorityQueue<Integer>[] D;
    private static int k;
 
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = null;
 
        st = new StringTokenizer(br.readLine().trim());
 
        n = Integer.parseInt(st.nextToken());
        int m = Integer.parseInt(st.nextToken());
        k = Integer.parseInt(st.nextToken());
 
        con = new ArrayList[n + 1];
        conv = new ArrayList[n + 1];
 
        for (int i = 1; i <= n; i++) {
            con[i] = new ArrayList<Integer>();
            conv[i] = new ArrayList<Integer>();
        }
 
        for (int i = 1; i <= m; i++) {
            st = new StringTokenizer(br.readLine().trim());
 
            int a = Integer.parseInt(st.nextToken());
            int b = Integer.parseInt(st.nextToken());
            int c = Integer.parseInt(st.nextToken());
 
            con[a].add(b);
            conv[a].add(c);
        }
        KthDijkstra(1);
 
        for (int i = 1; i <= n; i++) {
            if (D[i].size() < k)
                System.out.println(-1);
            else {
                System.out.println(D[i].poll());
            }
        }
    }
 
    private static void KthDijkstra(int a) {
        D = new PriorityQueue[n + 1];
        for (int i = 1; i <= n; i++) {
            D[i] = new PriorityQueue<Integer>(k, new Comparator<Integer>() {
                @Override
                public int compare(Integer a, Integer b) {
                    return b - a;
                }
            });
        }
        D[a].add(0);
        PriorityQueue<int[]> que = new PriorityQueue<int[]>(10, new Comparator<int[]>() {
            public int compare(int[] a, int[] b) {
                return a[0] - b[0];
            }
        });
 
        que.add(new int[] { 0, a });
        while (!que.isEmpty()) {
            int q = que.peek()[1];
            int d = que.peek()[0];
 
            que.poll();
            for (int i = 0; i < con[q].size(); i++) {
                int j = con[q].get(i);
                int v = conv[q].get(i);
                int c = d + v;
 
                if (D[j].size() < k) {
                    D[j].add(c);
                    que.add(new int[] { c, j });
                } else if (c < D[j].peek()) {
                    D[j].poll();
                    D[j].add(c);
                    que.add(new int[] { c, j });
                }
            }
        }
    }
}