[알고리즘] 백준 1865 - 웜홀 / 벨만 포드 알고리즘

문제

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

1865번: 웜홀

 

풀이

예전에도 시도했던 흔적이 있으나 실패로 남아있던 문제였다 . .  .

음수 가중치(웜홀)이 있어서 다익스트라로는 못 푸는데, 음수 가중치가 존재하는 경우에 최단경로를 찾는 알고리즘이 뭐였더라... ? ... 생각해보니 기억이 안 나서 결국 검색해봤고, 벨만 포드 알고리즘을 오랜만에 마주했다. 처음엔 이해가 잘 안 갔는데 ㅠ 내가 벨만 포드 알고리즘을 보면서 어려웠거나 이해 안 됐던 부분들을 적어보고자 한다.

 

 

https://www.youtube.com/watch?v=Ppimbaxm8d8&list=PLRx0vPvlEmdAghTr5mXQxGpHjWqSz0dgC&t=3

 

우선 처음엔 이 영상을 봤다. 이코테 영상은 이해하기 쉽게 돼있어서 참 좋다. 그런데... 이 영상을 보고나서도 이해가 안 되는 부분이 존재했다. 내가 참 멍청한 것 같다는 생각이 들었다...

 

 

내가 이해 안 됐던 부분은 다음과 같다

1. 왜 dist[v] != INF 인 경우에만 탐색을 하는가

2. 왜 n번째 돌 때 거리가 줄어드는 경우가 있으면 음수 사이클이 존재한다고 판단하는 것인가

 

 

1. 왜 dist[v] != INF인 경우에만 탐색을 하는가

간단하게 우리가 1에서 3으로 가는 경로를 찾는다고 생각해보자. 벨만포드에서는 어떤 한 노드를 기준으로 인접 노드를 찾는게 아니라 주어진 모든 '간선'을 기준으로 n-1번 탐색을 하게 된다.

따라서 내가 1에서 3으로 가는 최단 경로를 찾기 위해 dist[1] = 0으로 초기화 해두고, 나머지는 INF로 초기화 해 둔 후 간선을 탐색한다고 생각해 볼 때 모든 간선을 탐색 중에 2에서 3으로 가는 간선이 나오면 아직 1->2로 가는 간선이 확인되지 않아 2는 도달(?)하지 못한(시작지점인 1과 아직 연결되지 않은) 간선이기 때문에 dist[2]의 값은 INF일 것이고, 그럼 해당 간선의 값은 현재 탐색할 이유가 없게 되는 거다. 

 

2. 왜 n번째 돌 때 거리가 줄어드는 경우가 있으면 음수 사이클이 존재한다고 판단하는 것인가

n-1번 돌리면 최단거리를 찾을 수 있는 최소한의 탐색이 끝나는 것이다.

만약 사이클이 없다면 n번째 돌려도 각 노드의 최단거리에는 변함이 없을 것이다. 왜냐면 다익스트라를 생각해봐도... 뭐 다익스트라를 2-3번 돌린다고 최단경로가 달라지진 않잖아요..? 

근데 만약 

A -> B -3

B -> A 2

이런 간선이 있으면 사이클이 존재하는 것이고 A에서 B로 가는 최단경로가 처음엔 -3이었지만 여러번 돌렸을 땐 A->B->A->B 사이클로 인해 -4로 변경이 되는 경우가 생기는 거다. 따라서 이렇게 변경(더 작아지는 경우)이 생겼을 땐 음수 사이클이 있다고 판단하게 된다.

 

 

따라서 이 문제는 일반 벨만포드에서 살짝 변경을 해준 후 (시작 지점이 딱히 없기 때문에) 음수사이클이 존재하는가? 만을 체크하면 되는 문제여서 dist[start] != INF 조건을 없애고, 음수 사이클이 존재하는 경우(n번째에 최단경로 값이 더 작아지는 경우가 존재한다면)에 YES를 출력해주면 된다.

 

코드

TC = int(input())
for _ in range(TC):
    N,M,W = map(int,input().split())
    edges =[]

    for _ in range(M):
        S,E,T = map(int,input().split())
        edges.append((S,E,T))
        edges.append((E,S,T))
    for _ in range(W):
        S,E,T = map(int,input().split())
        edges.append((S,E,-T))

    times = [1e9 for _ in range(N+1)]
    times[1] = 0

    isCycle = False
    for i in range(N):
        for start,end,w in edges:
            distance = times[start] + w
            if distance < times[end]:
                if i == N-1:
                    isCycle = True
                times[end] = distance


    if isCycle:
        print("YES")
    else:
        print("NO")