[Boj_1854] K번째 최단경로 찾기

📎 문제 링크

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

 

▸ 문제

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

 

▸ 입력

첫째 줄에 n, m, k가 주어진다. (1≤n≤1000, 0≤m≤250000, 1≤k≤100, mk≤3000000) 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을 출력한다. 최단경로에 같은 정점이 여러 번 포함되어도 된다.

 

📍 문제 정보

• 💍  문제 레벨 : 플레티넘 4
• 🔔  문제 유형 : 자료구조, 그래프 이론, 최단 경로, 데이크스트라, 우선순위 큐
• 💬  풀이 언어 : JAVA

 

🤔 문제 풀이

이 문제는 1번 도시에서 i번 도시로 가는 k번째 최단 경로를 구하는 문제이다.

한 정점에서 다른 모든 정점의 최단 경로를 구해야 하므로, 다익스트라 알고리즘을 활용하여 해결할 수 있다.

 

예제 입력 1에서 2번째 최단 경로를 구해보자.

도시 (i)	1번째 최단 경로 (1 → i)	2번째 최단 경로 (1 → i)
1	0	-1 (경로 존재 x)
2	2 (1 → 2)	10 (1 → 5 → 2)
3	6 (1 → 2 → 3)	7 (1 → 3)
4	4 (1 → 2 → 4)	5 (1 → 4)
5	6 (1 → 5)	14 (1 → 2 → 3  → 5)

일반적인 다익스트라 알고리즘을 사용하면 1번째 최단 경로만 구할 수 있다.

그러나 이 문제에서는 k번째 최단 경로를 찾아야 하므로, 기존의 int[] dist 배열만으로는 해결할 수 없다.

따라서, PriorityQueue[] distQue 우선순위 큐 배열을 활용하여 1번 노드에서 각 노드까지의 k개의 최단 경로를 저장하는 방식으로 문제를 해결할 수 있다.

 

이때, 우선순위 큐 배열은 내림차순으로 정렬된다.

 

우선순위 큐 배열에 저장된 최단 경로의 개수가 k개 미만이라면, 새로운 경로를 추가한다.

이미 k개 이상의 최단 경로가 저장된 상태에서 새로운 경로가 발견되면, 기존 경로 중 가장 큰 값과 비교하여 새로운 경로가 더 짧을 경우에만 가장 큰 값을 제거하고 새로운 경로를 추가한다.

 

위 풀이를 코드로 작성해 보면 아래와 같다.

 

✔ 최종 코드

메모리 : 99924KB
시간 : 904ms

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

public class Main {
    static int n, k;
    static ArrayList<ArrayList<Pos>> list;
    static PriorityQueue<Integer>[] distQue;
    static public class Pos implements Comparable<Pos> {
        int end; int dist;
        public Pos(int end, int dist) {
            this.end = end; this.dist = dist;
        }
        @Override
        public int compareTo(Pos o) {
            return this.dist - o.dist;
        }
    }
    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()); // 도시의 개수
        int m = Integer.parseInt(st.nextToken()); // 도로의 수
        k = Integer.parseInt(st.nextToken()); // k번째 최단경로

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

        int a, b, c;
        for (int i = 0; i < m; i++) {
            st = new StringTokenizer(br.readLine());
            a = Integer.parseInt(st.nextToken());
            b = Integer.parseInt(st.nextToken());
            c = Integer.parseInt(st.nextToken());

            list.get(a).add(new Pos(b, c));
        }

        dijkstra();

        StringBuilder sb = new StringBuilder();
        for (int i = 1; i <= n; i++) {
            if (distQue[i].size() == k) {
                sb.append(distQue[i].peek()).append("\n");
            } else sb.append(-1).append("\n"); // k번째 경로 존재하지 않으면 -1
        }
        System.out.println(sb);
    }

    private static void dijkstra() {
        distQue = new PriorityQueue[n+1];
        // 내림차순
        for (int i = 0; i <= n; i++) {
            // 최대 k개의 경로 저장
            distQue[i] = new PriorityQueue<>((o1,o2)->o2-o1);
        }

        PriorityQueue<Pos> pq = new PriorityQueue<>();
        pq.offer(new Pos(1, 0));
        distQue[1].add(0);

        while (!pq.isEmpty()) {
            Pos now = pq.poll();
            int nowNode = now.end;

            for (Pos next : list.get(nowNode)) {
                int nextNode = next.end;
                int nextDist = now.dist + next.dist;

                // k개의 경로가 저장되지 않은 경우
                if (distQue[nextNode].size() < k) {
                    distQue[nextNode].add(nextDist); // 새로운 경로 추가
                    pq.offer(new Pos(nextNode, nextDist));
                } // 기존 k번째 경로보다 더 짧은 경로인 경우
                else if (distQue[nextNode].peek() > nextDist) {
                    distQue[nextNode].poll(); // 가장 긴 경로 제거
                    distQue[nextNode].add(nextDist); // 새로운 경로 추가
                    pq.offer(new Pos(nextNode, nextDist));
                }
            }
        }
    }
}

 

어렵다 어려워 ! 😂🔥