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

이번 강좌에서는 코틀린으로 K번째 최단 경로를 찾는 알고리즘 문제를 해결해보겠습니다. 이 문제는 그래프 이론의 중요한 부분인 최단 경로 알고리즘을 활용합니다. 주어진 그래프에서 K번째 최단 경로를 계산하는 것은 종종 복잡한 문제로 여겨지지만, 적절한 알고리즘과 자료 구조를 사용하면 효율적으로 해결할 수 있습니다.

문제 설명

그래프가 주어질 때, 두 점 A와 B 사이의 K번째 최단 경로를 찾는 문제입니다. 경로의 가중치는 양수이며, K는 1 이상 설정되어 있습니다. 경로는 중복될 수 있으며, K는 1부터 시작합니다. 즉, K=1일 경우 가장 짧은 경로를, K=2일 경우 두 번째로 짧은 경로를 의미합니다. 만약 K번째 경로가 존재하지 않는다면, “NO PATH”를 출력해야 합니다.

4 5 2
1 2 1
1 3 4
2 3 2
2 4 6
3 4 3
        

3
        

문제 해결을 위한 접근법

이 문제를 해결하기 위해서는 Dijkstra 알고리즘과 우선순위 큐를 활용하여 K번째 최단 경로를 찾는 방법을 사용합니다. 단일 출발점에서 여러 개의 최단 경로를 찾는 방식으로 확장할 수 있습니다. 기본 아이디어는 최단 경로를 구하는 과정을 K번 반복하여 각 단계에서 K번째 길이를 저장하는 것입니다.

1. 데이터 구조 설정

우선, 각 노드에서 K번째 최단 경로 정보를 저장할 수 있는 자료 구조를 설정합니다. 이를 위해 2D 배열을 사용할 수 있습니다. 각 배열의 인덱스는 노드 ID를, 두 번째 인덱스는 K번째 경로를 의미합니다.

val distance = Array(n + 1) { IntArray(k + 1) { Int.MAX_VALUE } }
    

2. 그래프 구축

그래프는 인접 리스트 형태로 표현합니다. 이를 위해 각 정점에 연결된 정점과 가중치를 저장합니다. 입력을 통해 그래프를 구성합니다.

val graph = mutableListOf>()
for (i in 0 until n + 1) {
    graph.add(mutableListOf())
}
for (i in 0 until m) {
    val (u, v, w) = readLine()!!.split(" ").map { it.toInt() }
    graph[u].add(Edge(v, w))
}
    

3. K번째 최단 경로를 찾는 알고리즘

우선순위 큐를 사용하여 최단 경로를 찾습니다. 각 경로를 큐에 추가하면서 거리를 업데이트합니다. K번째 최단 경로를 저장하기 위해 거리 배열을 적절히 관리합니다.

val queue = PriorityQueue(compareBy { it.weight })
distance[start][0] = 0
queue.add(Edge(start, 0))

while (queue.isNotEmpty()) {
    val current = queue.poll()
    val currentNode = current.node
    val currentWeight = current.weight
    
    for (edge in graph[currentNode]) {
        val nextNode = edge.node
        val newWeight = currentWeight + edge.weight
        if (distance[nextNode][k - 1] > newWeight) {
            distance[nextNode].sort()
            distance[nextNode][k - 1] = newWeight
            queue.add(Edge(nextNode, newWeight))
        }
    }
}
    

4. 결과 출력

마지막으로 K번째 최단 경로의 거리를 출력합니다. K번째 경로가 없을 경우에는 “NO PATH”를 출력합니다.

if (distance[end][k - 1] == Int.MAX_VALUE) {
    println("NO PATH")
} else {
    println(distance[end][k - 1])
}
    

코드 전체

fun main() {
    val (n, m, k) = readLine()!!.split(" ").map { it.toInt() }
    val graph = mutableListOf>()
    
    for (i in 0..n) {
        graph.add(mutableListOf())
    }
    
    for (i in 0 until m) {
        val (u, v, w) = readLine()!!.split(" ").map { it.toInt() }
        graph[u].add(Edge(v, w))
    }
    
    val distance = Array(n + 1) { IntArray(k + 1) { Int.MAX_VALUE } }
    val queue = PriorityQueue(compareBy { it.weight })
    
    distance[1][0] = 0
    queue.add(Edge(1, 0))

    while (queue.isNotEmpty()) {
        val current = queue.poll()
        val currentNode = current.node
        val currentWeight = current.weight
        
        for (edge in graph[currentNode]) {
            val nextNode = edge.node
            val newWeight = currentWeight + edge.weight

            if (distance[nextNode][k - 1] > newWeight) {
                distance[nextNode].sort()
                distance[nextNode][k - 1] = newWeight
                queue.add(Edge(nextNode, newWeight))
            }
        }
    }
    
    if (distance[n][k - 1] == Int.MAX_VALUE) {
        println("NO PATH")
    } else {
        println(distance[n][k - 1])
    }
}

data class Edge(val node: Int, val weight: Int)
    

결론

K번째 최단 경로 찾기는 그래프 문제 중 하나로, 다양한 알고리즘적 접근이 가능합니다. 위 예제에서는 Dijkstra 알고리즘을 변형하여 K번째 최단 경로를 찾는 방법을 설명했습니다. 실제로는 더욱 다양한 알고리즘이나 최적화 기법을 적용할 수 있으며, 문제에 따라 알고리즘을 선택하는 것이 중요합니다.

이번 강좌를 통해 알게 된 K번째 최단 경로 찾기 문제는 코딩 인터뷰에서도 자주 출제되는 문제이므로, 다양한 연습 문제를 통해 실력을 키우는 것이 좋습니다.