문제 설명

문제 분석

<aside> 💡 우선순위 큐로 선언하면 편리한 점

이 부분에서 최단 거리 배열의 객체 형식을 우선순위 큐로 선언했기 때문에 새로운 노드가 삽입됐을 때 별도의 정렬을 하지 않아도 자동으로 정렬돼 편리하게 구현할 수 있다는 장점이 있다.

</aside>

슈도코드

구현

public class K번째최단경로찾기_1854 {
    public static void main(String[] args) throws IOException {
        BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer tokenizer = new StringTokenizer(reader.readLine());
        int n = Integer.parseInt(tokenizer.nextToken()); // 도시의 수
        int m = Integer.parseInt(tokenizer.nextToken()); // 도로의 수
        int k = Integer.parseInt(tokenizer.nextToken()); // k번째 최단 경로를 구할거임
        Queue<Integer>[] distQ = new PriorityQueue[n+1];
        List<Node>[] cities = new ArrayList[n+1];
        for (int i = 0; i <= n; i++) {
            distQ[i] = new PriorityQueue<>(k, Collections.reverseOrder()); // 최솟값이 아닌 최댓값을 우선순위로 가지게 해야함
            cities[i] = new ArrayList<>();
        }

        for (int i = 0; i < m; i++) {
            tokenizer = new StringTokenizer(reader.readLine());
            int a = Integer.parseInt(tokenizer.nextToken());
            int b = Integer.parseInt(tokenizer.nextToken());
            int c = Integer.parseInt(tokenizer.nextToken());
            cities[a].add(new Node(b, c));
        }

        // 다익스트라
        Queue<Node> pq = new PriorityQueue<>();
        pq.add(new Node(1, 0));
        distQ[1].add(0);
        while (!pq.isEmpty()) {
            Node curNode = pq.poll();
            for(Node next : cities[curNode.target]){
                //저장된 경로가 K개가 안 될 때 그냥 추가
                if(distQ[next.target].size() < k) {
                    distQ[next.target].add(curNode.value + next.value);
                    pq.add(new Node(next.target, curNode.value + next.value));
                }
                //저장된 경로가 K개이고, 현재 가장 큰 값보다 작을 때만 추가
                else if(distQ[next.target].peek() > curNode.value + next.value) {
                    distQ[next.target].poll(); //기존 큐에서 Max 먼저 삭제
                    distQ[next.target].add(curNode.value + next.value);
                    pq.add(new Node(next.target, curNode.value + next.value));
                }
            }
        }

        for (int i = 1; i <= n; i++) {
            if(distQ[i].size() == k) {
                System.out.println(distQ[i].peek());
            } else {
                System.out.println(-1);
            }
        }
    }

    static class Node implements Comparable<Node> {
        int target;
        int value;

        public Node(int target, int value) {
            this.target = target;
            this.value = value;
        }

        @Override
        public int compareTo(Node o) {
            return this.value - o.value;
        }
    }
}