문제

이번 문제도 약간의 응용이 들어간 최단 거리 문제이다!
다익스트라로 최단 거리를 구할 때는 각 정점 당 가장 작은 하나의 값을 구하는 것이지만, k번째 최단 경로를 찾기 위해서는 각 정점 당 여러 값을 가져야한다고 생각했다.

문제 풀이

• dist 정보를 int[] 대신에 PriorityQueue<Integer>[]를 사용해서 담아야 한다.
  • 각 정점마다 거리값에 대한 큐를 가지고 있어야 하기 때문에
  • 내림차순 우선순위 큐
    -> 우선 순위 큐는 default가 오름차순이기 때문에 내림차순으로 만들어주기 위해서 -1을 곱해서 저장한다.
  • 큐의 크기는 K로 제한 (queue의 첫번째 원소가 k번째 최단 거리)
  • 우선순위 큐에 k개보다 적은 데이터가 있다면 데이터 삽입
  • 만약 k개가 있다면(꽉 차있는 상태), 가장 큰 값과 새로 들어오는 값을 비교해서 새로 들어오는 값이 더 작다면 원래 값을 삭제하고 데이터를 삽입한다.

• 한 정점을 여러 번 거쳐야 하기 때문에 visited는 필요없다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.PriorityQueue;
import java.util.StringTokenizer;

class Node implements Comparable<Node>{
    int v;
    int cost;
    public Node(int v, int cost){
        this.v = v;
        this.cost = cost;
    }
    @Override
    public int compareTo(Node o){
        return Integer.compare(this.cost, o.cost);
    }
}
class Main{
    public static ArrayList<Node>[] graph;
    // visited는 필요하지 않다.
    // int[] 대신에 PriorityQueue<Integer>[] 사용
    // 각 정점마다 거리값에 대한 큐를 가지고 있도록 한다.
    public static PriorityQueue<Integer>[] dist;
    public static int n;
    public static int m;
    public static int k;


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

        n = Integer.parseInt(st.nextToken());
        m = Integer.parseInt(st.nextToken());
        k = Integer.parseInt(st.nextToken());

        // 초기화
        graph = new ArrayList[n+1];
        dist = new PriorityQueue[n + 1];

        for(int i=1;i<=n;i++){
            graph[i] = new ArrayList<>();
            // 큐의 크기를 K로 제한
            dist[i] = new PriorityQueue<>(k);
        }

        // graph 생성
        for(int i=0;i<m;i++){
            st = new StringTokenizer(br.readLine());
            int a = Integer.parseInt(st.nextToken());
            int b = Integer.parseInt(st.nextToken());
            int c = Integer.parseInt(st.nextToken());
            graph[a].add(new Node(b, c));
        }

        // 다익스트라
        dijkstra(1);

        for(int i=1;i<=n;i++){
            if (dist[i].size() == k) System.out.println(dist[i].peek() * -1);
            else System.out.println(-1);
        }
    }
    public static void dijkstra(int start){
        // 그래프 탐색을 위한 우선 순위 큐
        PriorityQueue<Node> q = new PriorityQueue<>();
        q.add(new Node(start, 0));
        dist[start].add(0);

        while(!q.isEmpty()){
            // 현재 노드
            Node now = q.poll();

            // 인접한 노드
            for(Node next: graph[now.v]){
                if(dist[next.v].size() < k){ // 큐의 사이즈가 k보다 작은 경우에는 아무 데이터를 넣어도 상관없다.
                    dist[next.v].add((-1) * (now.cost + next.cost)); // 내림차순으로 처리하기 위해서 -1을 곱한다.
                    q.add(new Node(next.v, now.cost + next.cost));
                }
                else if((dist[next.v].peek() * -1) > (now.cost + next.cost)){ // 큐의 최대값과 비교했을 때 그보다 작으면 큐에서 최댓값을 삭제하고 지금 데이터를 저장한다.
                    dist[next.v].poll();
                    dist[next.v].add((-1) * (now.cost + next.cost));
                    q.add(new Node(next.v, now.cost + next.cost));
                }
            }
        }
    }

}

코드를 작성하면서, visited를 체크하지 않고 계속 큐에 넣어서 큐가 빌 때까지 while 문을 돌리면 무한 루프가 발생하지 않을까?라는 생각을 했다.
문제에서 주어지는 그래프 자체가 순환 그래프가 아닌 것을 가정으로 해서 무한 루프가 발생하는 경우는 없는 것 같다. ( 확인해보기 )

[참고]
https://pangtrue.tistory.com/273