[Python] 백준 1865번: 웜홀

https://www.acmicpc.net/problem/1865

1865번: 웜홀

import sys
input = sys.stdin.readline
INF = 1000000000


def bellmanFord():
    global isAvailable

    for i in range(1, n+1):
        for j in range(1, n+1):
            for target, wasted in info[j]:
                if dp[target] > wasted + dp[j]:
                    dp[target] = wasted + dp[j]

                    if i == n:
                        isAvailable = True


if __name__ == '__main__':
    # 입력
    tc = int(input())

    for _ in range(tc):
        n, m, w = map(int, input().split())

        info = [[] for _ in range(n+1)]

        # 도로
        for _ in range(m):
            s, e, t = map(int, input().split())

            info[s].append((e, t))
            info[e].append((s, t))

        # 웜홀
        for _ in range(w):
            s, e, t = map(int, input().split())

            info[s].append((e, -t))

        # 탐색
        isAvailable = False
        dp = [INF]*(n+1)
        bellmanFord()

        # 출력
        if isAvailable:
            print("YES")
        else:
            print("NO")

벨만포드를 1번도 이용해보지 않은 상태에서 문제를 풀어서 그 과정이 매우 험난했다. 결과적으로 말하면, dfs로 가능성이 있긴 했으나 시간초과로 풀지 못하였다. 따라서 벨만포드 알고리즘에 대해서 공부한 뒤 풀었다.

 

우선 입력은 info에, 도로는 양방향으로, 웜홀은 단방향으로 값을 넣어주는 식으로 하였다.

다음으로 벨만포드 함수를 통해 isAvailable 값을 바꿔주고, 이에 따라 출력을 해주는 방식이다. 벨만포드는, 우선 모든 노드에 대한 정보를 저장하는 리스트(dp)를 필요로 한다. 처음에는 모든 노드에 대해 무한대(INF) 값을 넣어주고, 시작점을 0을 넣은 채로 하는 것이 정석적인 방식이라고 한다. 하지만 해당 문제는 음의 싸이클을 찾는 것이 목적이기도 하고, 딱히 시작점이 주어지지 않았으므로 변형하여 코드를 작성한다.

bellmanFord() 함수의 j에 대한 for문을 먼저 살펴보자. 모든 노드에 대해서 j값이 변동되고, 현재의 노드의 모든 간선을 for문으로 또 돌아준다. 그리고 각 간선에 대해 조건문을 수행하는데, 해당 조건의 의미는, j를 기준으로, (가고자 하는 곳의 dp값) > (소비되는 시간) + (현재 노드의 dp값)이다. 즉, 모든 노드의 모든 간선에 대해서, 해당 조건문을 수행하고, dp 값을 최소값으로 만드는 것이다. 다음으로 if i == n이 있는데, 추후 설명하겠다.

이러한 반복문을 i에 대해서 1~n까지 반복하여 수행한다. 일반적인 벨만포드의 경우, 시작 지점의 값이 0이기 때문에 0과 인접한 노드부터 순차적으로 값이 변동되는 식이다. 하지만, 이 문제의 경우에는 앞에서 서술하였듯이, 음의 싸이클만 찾으면 된다. 따라서 처음에는 음수값을 가진 간선의 타겟 노드의 dp 값에 변동이 있을 것이고, 이것을 계속해서 반복하면서 음수 노드들의 인접 노드들이 변동된다. 아무튼 이것을 n번 수행하게 되면 음수 싸이클이 있는지를 확인할 수 있다. if i == n이라는 조건문이 핵심인데, 우선 음수 싸이클의 특징은 계속해서 음수값이 들어가기 때문에 dp값이 -∞가 된다는 것이 있다. 이것을 이용하는 것인데, 만약 음수 싸이클이 없었더라면, 마지막 반복 시 값의 변동이 없어야 한다. 이런 특성을 이용하여 저러한 조건문이 나온 것이다. 참고로 이것은 음수 싸이클을 체킹하기 위한 일반적인 방법으로 알려져 있다.