[백준/코틀린] 1916번: 최소비용 구하기

링크

1916번: 최소비용 구하기

풀이

그래프의 특정 시작점으로부터 모든 정점까지의 최단 거리를
다익스트라(Dijkstra) 알고리즘을 사용하여 구합니다.

출처: Wikipedia: Dijkstra’s algorithm

우선순위 큐에 (정점, 지금까지의 비용)을 넣고,
가장 비용이 작은 정점부터 꺼내며 최단 거리를 확정한 뒤, 인접한 정점들을 큐에 추가합니다.

음수 가중치가 없는 그래프이기 때문에,
정점이 처음 큐에서 꺼내질 때의 거리가 반드시 해당 정점까지의 최단 거리입니다.
더 짧은 경로가 존재한다면, 그 경로에 포함된 정점이 먼저 선택됐어야 하므로 모순입니다.
따라서 각 정점은 한 번만 갱신되며, 전체 시간 복잡도는 O(E log V)입니다.

• V: 정점의 수
• E: 간선의 수

[실전 알고리즘] 0x1D강 - 다익스트라 알고리즘

코드

import java.util.*

lateinit var graph: List<MutableList<Pair<Int, Int>>>
lateinit var distance: MutableList<Int>

fun dijkstra(start: Int) {
    val pq = PriorityQueue<Pair<Int, Int>>(compareBy { it.second })

    pq.add(start to 0)
    while (pq.isNotEmpty()) {
        val (cur, cd) = pq.poll()

        if (distance[cur] > cd) {
            distance[cur] = cd
            graph[cur].forEach { (next, w) ->
                pq.add(next to cd + w)
            }
        }
    }
}

fun main() {
    val n = readln().toInt()
    graph = List(n + 1) { mutableListOf() }
    distance = MutableList(n + 1) { Int.MAX_VALUE }

    repeat(readln().toInt()) {
        val (u, v, w) = readln().split(" ").map { it.toInt() }

        graph[u] += v to w
    }

    val (start, end) = readln().split(" ").map { it.toInt() }

    dijkstra(start)

    println(distance[end])
}