[6개월 안에 백준 플래티넘 달성하기] 10. 웜홀 1865 | 코틀린

웜홀 문제

문제

 

풀이

해당 문제는 한 지점 N에서 시작하여 다시 N까지 도달하였을 때 걸리는 시간이 음수가 나오는지 체크해 주는 문제이다.

즉 음의 간선이 존재하는 그래프 문제이므로 벨만포드를 응용하면 풀 수 있다.

 

벨만포드는 음의 간선과 음의 사이클이 존재할 경우 한 노드에서 다른 모든 노드까지의 최단 거리를 구하는 유용한 알고리즘이다.

 

풀이법은 다음과 같다.

1. N(노드개수) 번 동안 모든 간선을 돌면서 최단 거리를 갱신해 준다.
2. 이때 마지막 N번째에도 최단 거리가 갱신되면 음의 사이클이 존재한다고 판명한다.

N개의 노드가 있을 때 특정 노드 X의 최대 간선은 N-1개이다.
따라서 최대로 갱신될 수 있는 횟수는 N-1번이다.
하지만 음의 간선으로 인한 사이클이 존재하는 경우 이보다 더 많이 갱신될 수 있다.

 

 

아래 코드는 위와 같은 풀이법으로 푼 풀이이지만 시간초과가 발생한다.

그 이유는 바로 문제에서 시작 노드가 주어지지 않았기 때문이다.

시작 지점이 정해지지 않았기 때문에 N번의 벨만포드를 수행해야 되는데 이러면 시간초과가 발생한다.

import java.io.StreamTokenizer

fun main() = StreamTokenizer(System.`in`.bufferedReader()).run {
    fun input(): Int {
        nextToken()
        return nval.toInt()
    }

    var t = input()
    while (t-- > 0) {
        val N = input() // 노드 개수
        val M = input() // 간선
        val W = input() // 웜홀

        var arr = Array(N+1) {IntArray(N+1) {Int.MAX_VALUE} }

        // 간선 입력
        repeat(M) {
            val a = input()
            val b = input()
            val c = input()
            arr[a][b] = Math.min(arr[a][b], c)
            arr[b][a] = Math.min(arr[b][a], c)
        }
        // 웜홀 입력
        repeat(W) {
            val a = input()
            val b = input()
            val c = input() * -1
            arr[a][b] = Math.min(arr[a][b], c)
        }

        fun ballmanFold(start: Int): Boolean {
            val minDist = IntArray(N+1) {Int.MAX_VALUE}  // start 노드로부터 각 노드의 최소 거리
            minDist[start] = 0

            for (i in 1.. N) {

                for (start in 1..N) {
                    for (end in 1..N) {
                        if (arr[start][end] == Int.MAX_VALUE || start == end)
                            continue

                        if (minDist[start] != Int.MAX_VALUE && minDist[end] > minDist[start] + arr[start][end]) {
                            minDist[end] = minDist[start] + arr[start][end]

                            if (i ==N) return true
                        }
                    }
                }
            }
            return false
        }

        fun isCycle(): Boolean {
            for (i in 1..N) {
                if (ballmanFold(i)) {
                    return true
                }
            }
            return false
        }

        if (isCycle()) println("YES")
        else println("NO")
    }
}

 

 

 

해결 방안은 벨만포드를 한 번만 실행하게 만드는 것이다.

1. MAX를 계산 범주 안에 크기로 지정한다.
2. 기존에는 minDist [i]가 MAX인 경우 계산해주지 않았다. (최단 거리를 못 구하기 때문)
3. 하지만 해당 문제는 사이클의 존재여부만을 필요하기 때문에 minDist[i]가 MAX인 경우도 갱신해 준다.

 

 

해결된 코드이다.

import java.io.StreamTokenizer

fun 웜홀_밸만포드_풀이() = StreamTokenizer(System.`in`.bufferedReader()).run {
    fun input(): Int {
        nextToken()
        return nval.toInt()
    }

    val MAX = 100000000
    var t = input()
    while (t-- > 0) {
        val N = input() // 노드 개수
        val M = input() // 간선
        val W = input() // 웜홀

        var arr = Array(N+1) {IntArray(N+1) {MAX} }

        // 간선 입력
        repeat(M) {
            val a = input()
            val b = input()
            val c = input()
            arr[a][b] = Math.min(arr[a][b], c)
            arr[b][a] = Math.min(arr[b][a], c)
        }
        // 웜홀 입력
        repeat(W) {
            val a = input()
            val b = input()
            val c = input() * -1 // 음의 간선으로 변환
            arr[a][b] = Math.min(arr[a][b], c)
        }

        fun ballmanFold(): Boolean {
            val minDist = IntArray(N+1) {MAX}  // start 노드로부터 각 노드의 최소 거리
            minDist[1] = 0

            // N 번 돌면서
            for (i in 1.. N) {

                // 모든 간선을 돈다
                for (start in 1..N) {
                    for (end in 1..N) {
                        if (arr[start][end] == Int.MAX_VALUE)
                            continue

                        if ( minDist[end] > minDist[start] + arr[start][end]) {
                            minDist[end] = minDist[start] + arr[start][end]

                            // N번째에도 갱신이 된다는 것은 사이클이 존재한다는 것
                            if (i ==N) return true
                        }
                    }
                }
            }
            return false
        }

        if (ballmanFold()) println("YES")
        else println("NO")
    }
}

 

 

벨만포드 알고리즘으로 음의 사이클의 존재를 확인할 수 있다는 것을 알게 되었다.