자바 코딩테스트 강좌, K번째 최단 경로 찾기

K번째 최단 경로 찾기는 그래프 이론에서 많이 다루는 문제 중 하나입니다. 주어진 두 정점 사이에 K번째로 짧은 경로를 찾는 문제로,
그래프의 특성을 잘 이해하고 적절한 알고리즘을 적용하는 것이 중요합니다. 이 글에서는 이 문제의 정의와 해결 방법,
자바 코드 구현에 대해 자세히 설명하겠습니다.

문제 정의

주어진 방향 그래프에 대해 두 정점 A와 B 사이의 K번째 최단 경로를 찾는 문제를 고려해 봅니다.
이 때 “최단 경로”란 각 경로의 가중치 합이 최소인 경로를 의미합니다. K번째 최단 경로는 가장 짧은 경로를 첫 번째로 두고,
그 다음으로 짧은 경로, 그 다음 등을 차례로 비교하여 K번째를 찾는 것입니다.

입력

정점의 개수 N (1 ≤ N ≤ 100)
간선의 개수 M (1 ≤ M ≤ 500)
각 간선의 정보 (시작 정점, 도착 정점, 가중치)
시작 정점 A, 끝 정점 B, K

출력

정점 A에서 B까지의 K번째 최단 경로의 길이를 출력합니다.
K번째 최단 경로가 존재하지 않는다면 -1을 출력합니다.

알고리즘 개요

K번째 최단 경로 문제를 해결하기 위해 사용할 수 있는 알고리즘에는 Dijkstra 알고리즘의 변형이 있습니다.
일반적인 Dijkstra 알고리즘은 시작 정점에서 다른 모든 정점까지의 최단 경로를 찾습니다.
이를 K번째 최단 경로를 찾기 위해 약간의 변형을 적용해야 합니다.

문제 해결 접근법

1. 우선순위 큐(Priority Queue)를 사용하여 각 정점에서 K번째 최단 경로를 저장합니다.
2. 각 정점에 대해 최단 경로를 리스트 형태로 유지하며, 우선순위 큐를 통해 경로를 탐색합니다.
3. 경로를 탐색하면서 K번째 최단 경로를 갱신합니다.

단계별 설명

우선순위 큐 초기화: 각 정점에 대해 최단 경로를 K개까지 저장할 수 있는 구조체를 만든다.
Dijkstra 알고리즘 수행: 시작 정점에서 출발하여 인접한 정점으로의 가중치 합을 계산하고 우선순위 큐에 추가한다.
K번째 경로 확인: B 정점까지 도달한 경우, K번째 경로의 길이를 확인한다.

자바 코드 구현

아래는 K번째 최단 경로를 찾는 자바 코드입니다:


import java.util.*;

class Edge {
    int to, weight;

    Edge(int to, int weight) {
        this.to = to;
        this.weight = weight;
    }
}

class KthShortestPath {
    static final int INF = Integer.MAX_VALUE;

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        int N = sc.nextInt(); // 정점 개수
        int M = sc.nextInt(); // 간선 개수
        int K = sc.nextInt(); // K

        List[] graph = new ArrayList[N + 1];
        for (int i = 1; i <= N; i++) {
            graph[i] = new ArrayList<>();
        }

        for (int i = 0; i < M; i++) {
            int u = sc.nextInt();
            int v = sc.nextInt();
            int w = sc.nextInt();
            graph[u].add(new Edge(v, w));
        }

        int start = sc.nextInt();
        int end = sc.nextInt();

        System.out.println(findKthShortestPath(graph, N, start, end, K));
    }

    static int findKthShortestPath(List[] graph, int N, int start, int end, int K) {
        PriorityQueue pq = new PriorityQueue<>(Comparator.comparingInt(a -> a[0]));
        List[] minHeap = new ArrayList[N + 1];

        for (int i = 1; i <= N; i++) {
            minHeap[i] = new ArrayList<>();
        }

        pq.add(new int[]{0, start}); // {길이, 정점}
        
        while (!pq.isEmpty()) {
            int[] current = pq.poll();
            int currLength = current[0];
            int currNode = current[1];

            minHeap[currNode].add(currLength);
            if (minHeap[currNode].size() > K) {
                continue;
            }

            for (Edge edge : graph[currNode]) {
                int nextNode = edge.to;
                int nextLength = currLength + edge.weight;

                pq.add(new int[]{nextLength, nextNode});
            }
        }

        if (minHeap[end].size() < K) {
            return -1;
        }
        return minHeap[end].get(K - 1);
    }
}

예제 입력 및 출력

입력 예제

출력 예제

결론

K번째 최단 경로 찾기는 그래프를 이해하고, 적절한 알고리즘을 선택하여 문제를 해결하는데 큰 도움이 됩니다.
Dijkstra 알고리즘을 변형하여 K번째 최단 경로를 찾는 방법을 익히면 다양한 코딩 테스트에서 측면에서 유용하게 활용할 수 있습니다.

이 글을 통해 K번째 최단 경로 문제를 이해하고 자바로 구현하는 방법을 배웠습니다.
앞으로도 다양한 알고리즘 문제를 풀며 실력을 쌓아가시기 바랍니다!