코틀린 코딩테스트 강좌, 다익스트라

문제 풀이 과정

다익스트라 알고리즘은 그래프에서 한 정점에서 다른 정점까지의 최단 경로를 찾는 알고리즘입니다.
이 알고리즘은 음의 가중치가 없는 경우에만 올바르게 작동하므로, 가중치가 0보다 크거나 같은지 확인하는 것이 중요합니다.

아래는 코틀린을 이용한 다익스트라 알고리즘의 구현 과정입니다.

1. 그래프 표현

그래프를 표현하기 위해 인접 리스트를 사용합니다.
각 정점에 대해 그 정점에서 도달할 수 있는 정점과 그 간선의 가중치를 저장합니다.
예를 들어, 정수 배열을 이용하여 각 정점을 리스트로 표현할 수 있습니다.

    val graph = Array(N) { mutableListOf>() }
    

2. 입력 처리

입력 받은 간선 정보를 그래프에 추가합니다.
입력 형식에 따라서 반복문을 통해 각 간선의 정보를 저장합니다.

    for (i in 0 until M) {
        val (A, B, C) = readLine()!!.split(" ").map { it.toInt() }
        graph[A-1].add(Pair(B-1, C)) // A에서 B로 가는 C 가중치
    }
    

3. 다익스트라 알고리즘 구현

우선순위 큐를 이용하여 현재 최소 경로를 찾기 위한 알고리즘을 구현합니다.
다음은 다익스트라 알고리즘의 핵심 로직입니다.

    fun dijkstra(start: Int) {
        val distance = Array(N) { Int.MAX_VALUE }
        distance[start] = 0
        
        val pq = PriorityQueue>(compareBy { it.second })
        pq.add(Pair(start, 0))

        while (pq.isNotEmpty()) {
            val (current, dist) = pq.poll()

            if (dist > distance[current]) continue

            for (next in graph[current]) {
                val (nextNode, weight) = next
                val newDist = dist + weight

                if (newDist < distance[nextNode]) {
                    distance[nextNode] = newDist
                    pq.add(Pair(nextNode, newDist))
                }
            }
        }
    }
    

4. 결과 출력

최종적으로 도착점까지의 최단 거리를 계산하여 출력합니다.
도착점이 도달 불가능한 정점이라면, -1을 출력합니다.

    dijkstra(S - 1)
    val result = if (distance[E - 1] == Int.MAX_VALUE) -1 else distance[E - 1]
    println(result)
    

코드 전체

위의 로직을 바탕으로 하나의 완전한 코드는 아래와 같습니다.

    import java.util.*

    fun main() {
        val (N, M) = readLine()!!.split(" ").map { it.toInt() }
        val graph = Array(N) { mutableListOf>() }

        for (i in 0 until M) {
            val (A, B, C) = readLine()!!.split(" ").map { it.toInt() }
            graph[A - 1].add(Pair(B - 1, C))
        }

        val (S, E) = readLine()!!.split(" ").map { it.toInt() }

        fun dijkstra(start: Int) {
            val distance = Array(N) { Int.MAX_VALUE }
            distance[start] = 0

            val pq = PriorityQueue>(compareBy { it.second })
            pq.add(Pair(start, 0))

            while (pq.isNotEmpty()) {
                val (current, dist) = pq.poll()

                if (dist > distance[current]) continue

                for (next in graph[current]) {
                    val (nextNode, weight) = next
                    val newDist = dist + weight

                    if (newDist < distance[nextNode]) {
                        distance[nextNode] = newDist
                        pq.add(Pair(nextNode, newDist))
                    }
                }
            }
            return distance
        }

        dijkstra(S - 1)
        val result = if (distance[E - 1] == Int.MAX_VALUE) -1 else distance[E - 1]
        println(result)
    }