[백준 1854] K번째 최단경로 찾기 (JAVA)

문제

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

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

봄캠프를 마친 김진영 조교는 여러 도시를 돌며 여행을 다닐 계획이다. 그런데 김 조교는, '느림의 미학'을 중요시하는 사람이라 항상 최단경로로만 이동하는 것은 별로 좋아하지 않는다. 하지만 너무 시간이 오래 걸리는 경로도 그리 매력적인 것만은 아니어서, 적당한 타협안인 'k번째 최단경로'를 구하길 원한다. 그를 돕기 위한 프로그램을 작성해 보자.

입력

첫째 줄에 n, m, k가 주어진다. (1 ≤ n ≤ 1000, 0 ≤ m ≤ 2000000, 1 ≤ k ≤ 100) n과 m은 각각 김 조교가 여행을 고려하고 있는 도시들의 개수와, 도시 간에 존재하는 도로의 수이다.

이어지는 m개의 줄에는 각각 도로의 정보를 제공하는 세 개의 정수 a, b, c가 포함되어 있다. 이것은 a번 도시에서 b번 도시로 갈 때는 c의 시간이 걸린다는 의미이다. (1 ≤ a, b ≤ n. 1 ≤ c ≤ 1000)

도시의 번호는 1번부터 n번까지 연속하여 붙어 있으며, 1번 도시는 시작도시이다.

출력

n개의 줄을 출력한다. i번째 줄에 1번 도시에서 i번 도시로 가는 k번째 최단경로의 소요시간을 출력한다.

경로의 소요시간은 경로 위에 있는 도로들을 따라 이동하는데 필요한 시간들의 합이다. i번 도시에서 i번 도시로 가는 최단경로는 0이지만, 일반적인 k번째 최단경로는 0이 아닐 수 있음에 유의한다. 또, k번째 최단경로가 존재하지 않으면 -1을 출력한다. 최단경로에 같은 정점이 여러 번 포함되어도 된다.

예제 입력 1

5 10 2
1 2 2
1 3 7
1 4 5
1 5 6
2 4 2
2 3 4
3 4 6
3 5 8
5 2 4
5 4 1

예제 출력 1

-1
10
7
5
14

 

---

어렵네...😒

 

일반적인 다익스트라와는 달리 시작노드에서 도착노드까지 k 개의 최단거리를 구해내야한다. 이를 위해서는 아래의 두 가지 포인트를 생각해야한다.

 

1. k 개의 최단거리를 저장해야 하니까, 기존에 다익스트라 알고리즘에서 사용하던 1차원 int 형 배열을 dist 로 사용하면 안되겠다. 각각의 원소가 i 노드에 대한 k 개의 최단거리를 가지고 있으면 좋겠다. 근데 정렬 순서도 유지했음좋겟다.. 

▶ 우선순위큐 배열을 사용하자.

 

2. k 개의 최단거리를 계산하는 과정에서 같은 노드를 재방문하는 경우가 생긴다. 일반적인 다익스트라에서는 이러한 경우를 visited 배열로 방지했었는데.

▶ visited 배열을 사용하지 않는다.

 

3. k 개의 최단거리를 저장하도록 할까 아니면 모든 최단거리를 다 저장하도록 해서 출력할 때 k 개만 뽑아낼까? 당연히, k 개의 최단거리만 저장하는 것이 훨씬 효율적이다. 그러면 최단거리를 저장하는 로직을 어떻게 구현하지?

▶ 현재 노드에 해당하는 우선순위 큐 배열에 k 개 보다 작은 최단 거리만 저장되어 있다면, 다익스트라 알고리즘으로 발견한 새로운 경로를 저장한다. (우선순위 큐의 정렬 정책에 의해 자동으로 정렬된다.) 근데 만약에 k 개 이상의 최단거리가 저장되어있는데 새로운 경로가 발생한다면?

▶ 그러한 경우에는 현재 우선순위큐 배열에 저장된 top 과 비교한다. i 번째 노드에 대한 우선순위큐 배열의 top 은, "i 번째 노드에 도달하는 현재까지 저장된 최단 거리 중 가장 큰 값" 이다. 이 값보다 새로 계산된 경로가 작다면, top 을 poll() 해주고, 새로 계산된 경로를 add 해준다. 

▶ 이러한 과정으로 다익스트라 알고리즘을 돌려주면, 우선순위큐 배열의 size 가 k 이면 top 이 k 번째 최단거리이고, size 가 k 가 아니면 k 번째 최단거리는 존재하지 않는 것이다.

▶ 유의할 점은 문제에서 1 번노드에서 1 번노드로 향하는 최단거리는 0 이라고 정의한다는 것이다. 그러므로 다익스트라 알고리즘을 시작할 때, 초기 노드를 이를 고려하여 넣어주어야 한다.

 

 

import java.io.*;
import java.util.ArrayList;
import java.util.Comparator;
import java.util.PriorityQueue;
import java.util.StringTokenizer;

public class Main {
    static ArrayList<Node>[] graph;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer stk = new StringTokenizer(br.readLine());
        int n = Integer.parseInt(stk.nextToken()); // 노드 개수
        int m = Integer.parseInt(stk.nextToken()); // 에지 개수
        int k = Integer.parseInt(stk.nextToken()); // k
        // 먼저 그래프에 데이터를 저장하자.
        graph = new ArrayList[n + 1];
        for (int i = 0; i <= n; i++)
            graph[i] = new ArrayList<Node>();
        for (int i = 0; i < m; i++) {
            stk = new StringTokenizer(br.readLine());
            int a = Integer.parseInt(stk.nextToken());
            int b = Integer.parseInt(stk.nextToken());
            int cost = Integer.parseInt(stk.nextToken());
            graph[a].add(new Node(b, cost));
        }
        PriorityQueue<Integer>[] distQueue = new PriorityQueue[n + 1];
        Comparator<Integer> cp = new Comparator<Integer>() {
            @Override
            public int compare(Integer o1, Integer o2) {
                return o1 < o2 ? 1 : -1;
            }
        };
        for (int i = 0; i <= n; i++) {
            distQueue[i] = new PriorityQueue<>(k, cp);
        }
        PriorityQueue<Node> pq = new PriorityQueue<>();
        pq.add(new Node(1, 0)); // 시작점
        distQueue[1].add(0);
        while (!pq.isEmpty()) {
            Node now_node = pq.poll();
            for (Node cur : graph[now_node.toNode]) {
                // 연결관계 탐색
                if (distQueue[cur.toNode].size() < k) {
                    // 저장된 경로가 k 개 보다 작으면 경로 저장
                    distQueue[cur.toNode].add(now_node.w + cur.w);
                    pq.add(new Node(cur.toNode, now_node.w + cur.w));
                } else if (distQueue[cur.toNode].peek() > now_node.w + cur.w) {
                    // 저장된 경로가 k 개이고, 새로운 경로가 현재 가장 큰 값보다 작으면 추가
                    distQueue[cur.toNode].poll();
                    distQueue[cur.toNode].add(now_node.w + cur.w);
                    pq.add(new Node(cur.toNode, now_node.w + cur.w));
                }
            }
        }
        for(int i = 1 ; i <= n ; i++){
            if(distQueue[i].size()==k){
                bw.write(distQueue[i].peek()+"\n");
            } else bw.write("-1\n");
        }
        bw.flush();
        bw.close();
    }

    static class Node implements Comparable<Node> {
        int toNode;
        int w;

        public Node(int toNode, int w) {
            this.toNode = toNode;
            this.w = w;
        }

        @Override
        public int compareTo(Node v) {
            return this.w < v.w ? -1 : 1;
        }

    }
}