백준 11779번 코틀린

import java.util.PriorityQueue

fun main() {
    // 인풋
    val n = readLine()!!.toInt()
    val m = readLine()!!.toInt()
    val bus = Array<ArrayList<Pair<Int, Int>>>(n + 1) { ArrayList() } // [0] 버림
    repeat(m) {
        val (a, b, c) = readLine()!!.split(" ").map { it.toInt() }
        bus[a].add(Pair(b, c))
    }
    val (start, end) = readLine()!!.split(" ").map { it.toInt() }

    // 다익스트라 알고리즘 (우선순위 큐 사용)
    val dist = IntArray(n + 1) { Int.MAX_VALUE } // [0] 버림
    val from = IntArray(n + 1)                   // [0] 버림
    fun dijkstra() {
        val queue = PriorityQueue<Pair<Int, Int>> { a, b -> a.second - b.second }
        dist[start] = 0
        queue.add(Pair(start, dist[start]))

        while (queue.isNotEmpty()) {
            val head = queue.poll()

            if (head.second > dist[head.first]) { // 불필요한 탐색 줄여서 시간 절약 (큐에 (2, 500)가 들어왔는데 비용이 커서 계속 밀리는 중에 (2, 10)처럼 같은 2인데 효율 좋은 애가 먼저 들어온 경우 나중에 (2, 500)차례일 때 여기에 걸림)
                continue
            }

            for (next in bus[head.first]) {
                if (dist[next.first] > head.second + next.second) { // head.first 거쳤다가 next.first로 오는 게 기존의 길보다 더 빠르면
                    dist[next.first] = head.second + next.second
                    queue.add(Pair(next.first, dist[next.first]))

                    from[next.first] = head.first
                }
            }
        }
    }
    dijkstra()

    // 경로 출력 준비
    val path = ArrayList<Int>()
    path.add(end)
    while (true) {
        val last = path.last()

        if (from[last] != 0) {
            path.add(from[last])
        } else {
            break
        }
    }
    path.reverse()

    // 출력
    println("${dist[end]}\n${path.size}")
    path.forEach { print("$it " ) }
}

백준 1753번과 유사한 다익스트라 문제입니다.

그새 문제푼지 얼마나 됐다고 다익스트라 알고리즘이 기억이 잘 안 나는 상태였는데 다익스트라 알고리즘은 우선순위 큐를 이용해 구현한다, bfs와 유사하다, 그러나 visited는 사용하지 않는다, dist라는 테이블을 사용한다라는 사실만 떠올려서 구현하니 생각보다 빠르게, 그리고 정확하게 구현할 수 있었습니다.

 

다만 이 문제는 1753번 문제와는 다르게 단순히 비용만 계산하는 게 아니라 왔던 경로들을 출력해야하기 때문에 어느 경로에서 왔는지 알 수 있어야 하는데 이는 from 배열과 path라는 ArrayList를 만들어서 해결하였습니다.

 

from에는 i번째 마을은 어느 마을에서 왔는지 적는 것이고, path라는 배열은 그 from을 따라서 올라가면서 최종적으로 from이 0인 start 마을까지 올라가며 add 합니다.

그렇기 때문에 path는 5 4 1 이렇게 거꾸로 되어있으므로 마지막에 path.reverse()를 통해 1 4 5로 바꾸어준 후 출력하였습니다.