BOJ_1854 : K번째 최단경로 찾기

👉 문제링크

---

🔸 문제 분석 🔸

• 1번 도시부터 다른 도시로 가는 K번째 최단 거리를 구해야 한다.
• K번째 최단 경로가 없으면 -1 출력한다.

🔸 문제 풀이 🔸

• 한 노드부터 다른 노드까지의 최단 거리를 구하므로, 다익스트라 (Dijkstra) 알고리즘을 선택한다.
• 일반적인 다익스트라와 다르게, 거리를 업데이트이트 하지 않고 우선 순위 큐에 다시 넣는다.
• 무한 순환 혹은 너무 많은 원소가 생기지 않도록, K개 까지만 거리를 구한다.

🔸 코드 🔸

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

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringBuilder sb = new StringBuilder();
        StringTokenizer st = new StringTokenizer(br.readLine());

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

        ArrayList<ArrayList<int[]>> adjList = new ArrayList<>();
        ArrayList<ArrayList<Integer>> dist = new ArrayList<>();

        for (int i = 0; i <= n; i++) {
            adjList.add(new ArrayList<>());
            dist.add(new ArrayList<>());
        }

        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());
            adjList.get(a).add(new int[]{b, c});
        }

        PriorityQueue<int[]> pq = new PriorityQueue<>(Comparator.comparingInt(a -> a[1]));

        pq.offer(new int[]{1, 0});

        while (!pq.isEmpty()) {
            int[] now = pq.poll();

            if (dist.get(now[0]).size() >= k) {
                continue;
            }

            dist.get(now[0]).add(now[1]);

            for (int[] a : adjList.get(now[0])) {
                pq.offer(new int[]{a[0], now[1] + a[1]});
            }
        }

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

        bw.write(sb.toString());
        bw.flush();
    }
}

🔸 코드 해석 🔸

• 간선 정보를 저장하기 위한 인접 리스트 adjList를 사용했다.
• K개의 최단 경로를 저장하기 위한 리스트 dist를 사용했다.
• 일반적인 방문 체크 대신, 최단 경로의 개수가 K개가 되지 않을 때 까지 다익스트라 알고리즘을 사용한다.

---

🔸 end 🔸

• 플레티넘 문제라고 많이 걱정했는데, 다익스트라 알고리즘을 조금만 변형하면 된다는 아이디어가 떠오른다면 금방 풀리는 문제였다.
• 나는 우선순위 큐에서 나오는 거리가 해당 노드까지 가는 '현재의 최단거리'로 생각하고 풀이했는데, 이게 최단 거리를 확실히 보장하는지는 의문이다. (백준 게시판에 질문을 남겨놨다.)
  • 다른 풀이로 dist를 그냥 ArrayList가 아닌 우선 순위 큐의 배열로 구현하는 방법도 있었다. 이 경우엔 확실히 K번째 거리를 보장한다.
• 코드를 다듬으며 여러번 제출했는데, 알고리즘이 같으니 시간이나 메모리가 비슷하다. 근소한 수치 차이는 그냥 서버 상태의 차이인 것 같다.