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

문제 설명

주어진 그래프에서 두 노드 A, B 사이의 K번째 최단 경로를 찾는 문제입니다.
그래프는 가중치가 있는 방향 그래프입니다. K번째 최단 경로란 A에서 B로 가는
경로 중 가중치의 합이 K번째로 작은 경로를 의미합니다.
K는 양의 정수이며, K는 항상 1보다 크거나 같습니다.

입력 설명

입력으로는 첫 번째 줄에 정수 N (1 ≤ N ≤ 100)과 정수 M (1 ≤ M ≤ 1000)이 주어집니다.
이때 N은 노드의 개수, M은 간선의 개수를 나타냅니다.
이어서 M개의 줄에는 세 개의 정수 U, V, W가 주어지며, 이는 노드 U에서 노드 V로 가는 가중치 W인 간선을 의미합니다.
마지막 줄에는 두 개의 정수 K, A, B가 주어집니다. K는 몇 번째 최단 경로를 찾을 것인지,
A는 시작 노드, B는 도착 노드를 의미합니다.

출력 설명

K번째 최단 경로의 가중치 합을 출력합니다. 만약 K번째 최단 경로가 존재하지 않는 경우 -1을 출력합니다.

문제 풀이 과정

이 문제를 해결하기 위해 다양한 방법이 있지만, ‘다익스트라 알고리즘’ 변형 방법을 사용할 수 있습니다.
기본적으로 다익스트라 알고리즘은 최단 경로를 찾기 위해 사용되지만,
일정 횟수의 최단 경로를 찾기 위해 우선순위 큐(Priority Queue)와 경로 리스트를 활용할 수 있습니다.
다음은 그 과정입니다.

1. 그래프 표현

그래프를 인접 리스트 형태로 표현합니다. 각 노드에 대해 연결된 노드와 그 가중치를 저장합니다.

2. 우선순위 큐 사용

최단 경로를 찾기 위해 우선순위 큐를 사용하여 현재 노드에서의 경로의 가중치를 관리합니다.
K번째 경로를 찾기 위해 각 노드의 경로 리스트를 유지합니다.

3. 경로 계산

시작 노드에서 출발하여, 각 노드에 대한 경로를 탐색합니다.
이때, 각 경로의 가중치 합이 작을수록 우선순위가 높게 설정되며,
이 과정을 K번째 최단 경로가 발견될 때까지 반복합니다.

4. 결과 출력

K번째 최단 경로의 가중치 합이 성공적으로 계산되면 해당 값을 출력합니다.
경로가 존재하지 않는 경우 -1을 출력합니다.

스위프트 코드 구현

아래는 위에서 설명한 방법을 사용한 스위프트 코드입니다.

import Foundation

struct Edge {
    let to: Int
    let weight: Int
}

func kthShortestPath(n: Int, edges: [[Edge]], k: Int, start: Int, end: Int) -> Int {
    var paths = [[Int]](repeating: [], count: n + 1)
    var minHeap = [(weight: Int, node: Int)]()
    
    // (0, 시작 노드) 삽입
    minHeap.append((0, start))
    
    while !minHeap.isEmpty {
        // 가장 가중치가 작은 노드 꺼내기
        minHeap.sort { $0.weight < $1.weight }
        let current = minHeap.removeFirst()
        
        // 경로 저장
        paths[current.node].append(current.weight)
        
        // k번째 경로가 구해졌다면 종료
        if paths[end].count == k {
            return current.weight
        }
        
        // 인접 노드 탐색
        for edge in edges[current.node] {
            minHeap.append((current.weight + edge.weight, edge.to))
        }
    }
    
    // K번째 경로가 존재하지 않음
    return -1
}

// 입력
let n = 5 // 노드 개수
let m = 7 // 간선 개수
let edges = [
    1: [Edge(to: 2, weight: 10), Edge(to: 3, weight: 5)],
    2: [Edge(to: 3, weight: 2), Edge(to: 4, weight: 1)],
    3: [Edge(to: 2, weight: 3), Edge(to: 4, weight: 9)],
    4: [Edge(to: 5, weight: 2)],
    5: []
]
let k = 3 // K번째 경로
let start = 1 // 시작 노드
let end = 5 // 도착 노드

// 함수 호출
let result = kthShortestPath(n: n, edges: edges, k: k, start: start, end: end)
print(result) // 결과 출력
    

마무리

K번째 최단 경로 찾기 문제는 알고리즘 문제 해결의 중요한 기술 중 하나입니다.
다익스트라 알고리즘과 우선순위 큐를 활용하여 문제를 효율적으로 해결할 수 있습니다.
또한, 이와 같은 문제는 실제 면접에서도 종종 접할 수 있으므로 충분한 연습이 필요합니다.
이번 강좌를 통해 K번째 최단 경로 찾기 문제 이해의 기초가 되기를 바랍니다.