[kotlin] 코틀린으로 최단 경로 알고리즘 구현하기

14 Dec 2023

kotlin

최단 경로 알고리즘은 그래프에서 노드 사이의 최단 경로를 찾는 알고리즘이다. 이를 통해 교통 네트워크, 길찾기, 배달 경로 최적화 등 다양한 분야에서 활용된다. 이번 포스트에서는 코틀린을 사용하여 그래프의 최단 경로를 찾는 알고리즘을 구현하는 방법을 알아보겠다.

다익스트라 알고리즘

다익스트라 알고리즘은 하나의 시작 정점으로부터 모든 다른 정점까지의 최단 경로를 찾는 알고리즘이다. 이 알고리즘은 다음과 같은 단계로 동작한다.

시작 정점을 선택하고, 해당 정점까지의 최단 거리를 0으로 설정한다.
시작 정점을 제외한 모든 정점까지의 최단 거리를 무한대로 초기화한다.
방문하지 않은 정점 중에서 최단 거리에 있는 정점을 하나씩 방문하면서 해당 정점을 경유지로 하여 인접한 정점까지의 거리를 업데이트한다.
모든 정점을 방문할 때까지 3번 단계를 반복한다.

코틀린으로 구현

아래는 코틀린으로 다익스트라 알고리즘을 구현한 예시코드이다.

class Dijkstra(graph: Map<Int, List<Pair<Int, Int>>>) {
    private val distances = mutableMapOf<Int, Int>()

    init {
        graph.keys.forEach { distances[it] = Int.MAX_VALUE }
        distances[0] = 0

        val visited = mutableSetOf<Int>()
        while (visited.size < graph.size) {
            val vertex = distances
                .filter { it.key !in visited }
                .minByOrNull { it.value }!!
                .key
            visited.add(vertex)
            graph[vertex]?.forEach {
                val distance = distances[vertex]!! + it.second
                if (distance < distances[it.first]!!) {
                    distances[it.first] = distance
                }
            }
        }
    }

    fun getShortestPathTo(vertex: Int): Int {
        return distances[vertex] ?: -1
    }
}

fun main() {
    val graph = mapOf(
        0 to listOf(1 to 4, 2 to 2),
        1 to listOf(2 to 5),
        2 to listOf(3 to 3),
        3 to emptyList()
    )

    val dijkstra = Dijkstra(graph)
    println(dijkstra.getShortestPathTo(3)) // Output: 7
}

위 코드는 그래프를 입력으로 받아 다익스트라 알고리즘을 실행하고, 주어진 정점까지의 최단 거리를 반환하는 예시이다.

이렇게 코틀린을 사용하여 최단 경로 알고리즘을 구현할 수 있다. 최단 경로 알고리즘은 실제 산업 분야뿐만 아니라 다양한 서비스에서 활용되고 있으며, 코틀린을 이용하여 구현하면 간결하고 효율적인 코드를 작성할 수 있다.

더 많은 참고 자료는 코틀린 공식 문서에서 확인할 수 있다.