[ 백준 ][ 골드3 ] 1865번 - 웜홀 (Python 파이썬)

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

1865번: 웜홀

 

코드

---

def bf(start):
    dis = [0] * (n + 1)
    for i in range(n):
        for way in graph:
            cur,next_node,cost = way
            if dis[next_node] > dis[cur] + cost:
                dis[next_node] = dis[cur] + cost
                if i >= n-1:
                    return False
    return True

for _ in range(int(input())):

    n,m,w = map(int,input().split())
    graph = []

    for _ in range(m):
        s,e,t = map(int,input().split())
        graph.append((s,e,t))
        graph.append((e,s,t))

    for _ in range(w):
        s,e,t = map(int,input().split())
        graph.append((s,e,-t))

    print("YES" if not bf(1) else "NO")

 

풀이

---

음의 간선이 주어진 그래프이기 때문에 벨만 포드 알고리즘을 사용한다.

 

처음에는 문제에서 시작지점을 주어주지 않고 어떤 지점이든 상관없다고 하길래 모든 지점에 대해서 벨만 포드 알고리즘을 사용하려 했다.

모든 점(n)을 탐색하며 해당 지점을 출발점으로 지정하려 했는데 생각해보니 음의 간선이 존재하는 지만 확인하면 되기 때문에 출발점은 의미가 없었다. 그저 n번 모든 간선을 탐색하여 거리가 n번째에도 줄어든다면 음의 싸이클이 존재하는 것이다.

음의 싸이클이 존재하면 True, 존재하지 않는다면 False이다.

 

문제가 '타임머신'이라는 문제와 비슷한데 두 문제의 차이점은 '출발점'이다.

타임머신은 한 점에서 출발하여 그 출발점과 연결된 점들 사이를 오가고 그 안에서 음의 싸이클을 찾지만 이 문제는 모든 점에 대해서 찾기 때문에 몇 가지 조건이 빠지게 된다. (dis[node] != 1e9)

 

벨만 포드 알고리즘에서 N번째까지 확인하는 이유는 뭘까?

이는 어떤 한 노드를 출발점이라고 가정하였을 때, 그 노드가 최단거리로 갈 수 있는 가장 많은 점은 ( 모든 점(N) - 1 )개 이기 때문이다.

물론 테스트 케이스에 따라 아주 짧은 거리로도 자기 자신에게 돌아올 수 있겠지만 우린 항상 최악의 경우를 생각하고 코드를 작성해야 하며 벨만 포드에서 최악의 경우는 모든 점을 다 거치고 자기 자신에게 돌아왔을 때이다.

모든 점을 다 거치게 되면 그때의 거리 배열이 최단거리 배열이 되는데 여기서 한 번 더 지났을 때 거리가 줄어든다면 그것은 음의 싸이클이라 판단할 수 있다.