[백준] 11657번 타임머신

백준 - 11657번 타임머신

문제

N개의 도시가 있다. 그리고 한 도시에서 출발하여 다른 도시에 도착하는 버스가 M개 있다. 각 버스는 A, B, C로 나타낼 수 있는데, A는 시작도시, B는 도착도시, C는 버스를 타고 이동하는데 걸리는 시간이다. 시간 C가 양수가 아닌 경우가 있다. C = 0인 경우는 순간 이동을 하는 경우, C < 0인 경우는 타임머신으로 시간을 되돌아가는 경우이다.

1번 도시에서 출발해서 나머지 도시로 가는 가장 빠른 시간을 구하는 프로그램을 작성하시오.

접근 방법

각 도시 별 가장 빠른 시간을 구하는 문제이므로, 다익스트라와 벨만포드를 떠올릴 수 있다.
간선 중에 음수 가중치가 존재하므로 벨만포드를 사용하여 문제를 풀이한다.

벨만포드는 정점 N번을 반복하는데 이 이유는, 적어도 N-1번째에서 간선 N-1개를 갖게 된다. 따라서 N번 째에 값이 갱신되는 경우가 있다면 음수 순환이 생겼다고 말할 수 있게 되므로 N 번을 반복한다.

코드

class IO11657 {
    private val br = System.`in`.bufferedReader()
    private val bw = System.out.bufferedWriter()

    fun getNM() = br.readLine().split(" ").map { it.toInt() }
    fun getRow() = br.readLine().split(" ").map { it. toInt() }
    fun close() = bw.close()
    fun write(message: String) = bw.write(message)
}

fun main() {
    val io = IO11657()
    val (N, M) = io.getNM()
    val arr = Array(M) { io.getRow() }
    val distance = Array(N + 1) { Long.MAX_VALUE }
    var flag = false

    distance[1] = 0

    for (i in 1..N) {
        for (j in 0 until M) {
            val (curNode, nextNode, cost) = arr[j]

            if (distance[curNode] != Long.MAX_VALUE && distance[nextNode] > distance[curNode] + cost) {
                distance[nextNode] = distance[curNode] + cost
                if ( i == N ) {
                    flag= true
                }
            }
        }
    }

    if (flag) {
        io.write( (-1).toString())
        io.close()
    } else {
        for (idx in 2..N) {
            if (distance[idx] == Long.MAX_VALUE) {
                io.write("-1\n")
            } else {
                io.write("${distance[idx]}\n")
            }
        }
        io.close()
    }

}