[kotlin] 코틀린으로 다익스트라 알고리즘 작성하기

14 Dec 2023

kotlin

다익스트라 알고리즘은 그래프 내의 한 정점에서 다른 모든 정점까지의 최단 경로를 구하는 알고리즘입니다. 코틀린으로 이 알고리즘을 구현하는 방법을 살펴보겠습니다.

그래프 클래스 정의

우선 그래프를 표현하기 위한 클래스를 정의합니다. 각 정점과 해당 정점으로부터의 간선 정보를 저장할 수 있는 구조를 만들어야 합니다.

class Graph {
    private val adjacencyList = mutableMapOf<Int, MutableMap<Int, Int>>()

    fun addEdge(source: Int, destination: Int, weight: Int) {
        adjacencyList.getOrPut(source, { mutableMapOf() })[destination] = weight
    }

    fun getWeight(source: Int, destination: Int): Int {
        return adjacencyList[source]?.get(destination) ?: Int.MAX_VALUE
    }
}

다익스트라 알고리즘 구현

이제 다익스트라 알고리즘을 구현할 차례입니다. 우선 각 정점까지의 최단 거리를 저장하는 배열과 방문 여부를 저장하는 배열을 초기화합니다. 그리고 우선순위 큐를 사용하여 최단 거리가 가장 짧은 정점을 선택하도록 합니다.

import java.util.*

fun dijkstra(graph: Graph, source: Int): Map<Int, Int> {
    val distances = mutableMapOf<Int, Int>()
    val visited = mutableMapOf<Int, Boolean>()
    val queue = PriorityQueue<Pair<Int, Int>>(compareBy { it.second })

    distances[source] = 0
    queue.add(source to 0)

    while (queue.isNotEmpty()) {
        val (current, currentDistance) = queue.poll()

        if (visited[current] == true) continue
        visited[current] = true

        for ((neighbor, weight) in graph.adjacencyList[current] ?: emptyMap()) {
            val newDistance = currentDistance + weight
            if (distances[neighbor] == null || distances[neighbor] ?: Int.MAX_VALUE > newDistance) {
                distances[neighbor] = newDistance
                queue.add(neighbor to newDistance)
            }
        }
    }

    return distances
}

예제 실행하기

fun main() {
    val graph = Graph()
    graph.addEdge(1, 2, 2)
    graph.addEdge(1, 3, 4)
    graph.addEdge(2, 3, 1)
    graph.addEdge(2, 4, 7)
    graph.addEdge(3, 4, 3)

    val source = 1
    val distances = dijkstra(graph, source)

    println("최단 거리:")
    for ((destination, distance) in distances) {
        println("$source 에서 $destination 까지의 거리: $distance")
    }
}

이제 코드를 실행하면 각 정점까지의 최단 거리가 출력될 것입니다. 다익스트라 알고리즘을 코틀린으로 성공적으로 구현했습니다!

그래프 클래스 정의

다익스트라 알고리즘 구현

예제 실행하기

참고 자료