[BOJ][Java] 1854번 K번째 최단경로 찾기

문제 설명

문제 링크 : https://www.acmicpc.net/problem/1854

 

이 문제는 시작 정점부터 각각의 정점까지의 최단 거리를 찾는 다익스트라 알고리즘을 변형한 문제이다.

단순히 최단 거리가 아닌 k번째 최단 경로를 구해야 한다.

일반적으로 다익스트라 알고리즘은 각 정점까지 최단거리만을 저장하는 배열을 가지고 있는데

이 문제를 해결하기 위해서는 각 정점까지의 거리 중 k번째로 짧은 거리까지 저장할 수 있는 

자료구조가 필요하다. 여기서 PriorityQueue를 사용하면 매번 따로 처리해주지 않아도

편하게 k번째 최단거리를 구할 수 있다.

 

일반적인 다익스트라 알고리즘 문제에서는 인접 리스트를 구현해서 푸는 것이 더 편하지만

이 문제를 해결하기 위해서는 이런 인접 행렬을 이용해야 한다.

arr[1][2] = 2의 의미는 1번 정점으로부터 2번 정점까지 가는데 시간이 2 소요된다는 의미이다.

 

각 정점까지의 최소 거리를 구하는 다익스트라 알고리즘과 다르게 

이 문제는 각 정점까지의 k번째 최단거리를 구하기 위해 정점까지의 거리를 저장하는 배열을 

우선순위 큐로 구현했다.

 

이때 배열에 들어있는 우선순위 큐의 사이즈를 체크하고 만약

사이즈가 k보다 작다면 무조건 (현재 정점 + 해당 정점까지의 거리)를 추가하고,

만약 k와 같다면 현재 우선순위큐에서 가장 큰 값과  (현재 정점 + 해당 정점까지의 거리) 값을

비교한뒤 만약 (현재 정점 + 해당 정점까지의 거리) 이 더 작다면 가장 큰 값을 제거하고

(현재 정점 + 해당 정점까지의 거리) 값을 추가하면 된다.

 

package boj;

import java.util.*;
import java.io.*;

public class BOJ1854 {
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        int n = Integer.parseInt(st.nextToken());
        int m = Integer.parseInt(st.nextToken());
        int k = Integer.parseInt(st.nextToken());
        List<PriorityQueue<Integer>> dist = new ArrayList<>();
        PriorityQueue<Node> pq = new PriorityQueue<>((o1,o2) -> o1.cost - o2.cost);

        int[][] arr = new int[n+1][n+1];
        for(int i = 0; i < m; i++){
            st = new StringTokenizer(br.readLine());
            int u = Integer.parseInt(st.nextToken());
            int v = Integer.parseInt(st.nextToken());
            int w = Integer.parseInt(st.nextToken());
            arr[u][v] = w;
        }

        for(int i = 0; i < n+1; i++){
            dist.add(new PriorityQueue<>((o1,o2) -> o2 - o1));
        }

        pq.add(new Node(1, 0));
        dist.get(1).add(0);

        while(!pq.isEmpty()){
            Node now = pq.poll();

            for(int i = 1; i <= n; i++){
                if(arr[now.node][i] > 0){
                    if(dist.get(i).size() < k){
                        dist.get(i).add(now.cost + arr[now.node][i]);
                        pq.add(new Node(i, now.cost + arr[now.node][i]));
                    }else if(dist.get(i).peek() > now.cost + arr[now.node][i]){
                        dist.get(i).poll();
                        dist.get(i).add(now.cost + arr[now.node][i]);
                        pq.add(new Node(i, now.cost + arr[now.node][i]));
                    }
                }
            }
        }

        StringBuilder sb = new StringBuilder();

        for(int i = 1; i < dist.size(); i++){
            if(dist.get(i).size() < k) sb.append(-1).append("\n");
            else sb.append(dist.get(i).peek()).append("\n");
        }

        System.out.println(sb);
    }
    static class Node{
        int node;
        int cost;

        public Node(int node, int cost){
            this.node = node;
            this.cost = cost;
        }
    }
}