[BOJ] 웜홀 (G3, 1865) - 벨만-포드 알고리즘 튜토리얼

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

그 동안 학습한 최단 경로 구하기 알고리즘은 다음과 같다.
- 다익스트라 알고리즘 : 힙 기반, 간선이 모두 양의 가중치일 때만 사용 가능 
- 플로이드-워셜 알고리즘 : DP기반, 모든 거리를 구해주지만 V^3 만큼의 시간복잡도....

이 문제는 일단 웜홀의 존재 이유 때문에 다익스트라는 사용 불가능하다.
게다가 이 문제는 여러 번 워프를 타면서 시간을 돌릴 수 있는지?를 물어본다.

플로이드-워셜 알고리즘에서 음의 가중치를 갖는 루프를 찾기 위해서는 자기 자신으로 돌아오는 지점의 , 즉 dp[i][i]<0 임의 존재성을 보이면 된다. 문제는 시간 복잡도 때문에 터져서 불가. 이 문제는 벨만-포드 알고리즘을 사용해야만 한다.

 

벨만-포드 알고리즘의 핵심은 모든 edge를 항상 활용한다. 모든 edge를 돌면서, (꼭지점 개수 만큼) 해당 간선으로 거리가 작아질 수 있는지 항상 확인한다. 그리고 이를 갱신한다. 모든 edge를 돌기 때문에, 거리가 줄어드는 것도 보장된다.\

그런데 문제가 하나 발생한다. 모두 양의 가중치이면 문제가 없겠지만, 음이면?  음수면 무한히 돌아서 가중치가 작아지는 현상이 발생할 것이다. 따라서 이를 막아주는 방법이, 루프를 끊어 주는 것이다. 하지만 어떻게?

양수일 때를 상상해보자. 만일 한 지점에서 다른 지점으로 가는 최단 거리가 있다면, 최단 거리까지 가는 edge 개수는 정말 많아야 꼭지점-1이다. 음수여도 더 줄여줄 방법이 없다면 이는 확정적이다. 굳이 더 돌아갈 이유가 없으니까. 따라서, 꼭지점-1 보다 더 많은 거리 갱신이 발생한다? 루프 확정이다.! 이 루프 찾는거는 시작점이 어디어도 상관이 없다. 존재만 하면 V번째에 갱신 발생하면 음의 루프 존재 확정이다.

이 문제는 그러한 루프가 있습니까? 를 묻는 문제다.

# 벨만 포드 알고리즘을 araboza
# 한 노드에서 다른 노드 까지의 최단 거리를 알아내는 또 다른 알고리즘
# 이번엔 음의 가중치도 가능하다. 매 단계마다, 모든 간선을 확인하며 최단 거리를 구해 나가서.
# 음의 가중치가 들어가면 이걸 또 타서 줄일 수 있다. 문제는 음의 가중치 때문에 음의 사이클이 터지면 어떡함?
# 지금까지의 이웃까지의 거리보다, 현재 정점을 거치는게 유리하면..? 체크.

import sys
input = sys.stdin.readline
def bellman_ford(vertex, edge_list, dist):
    dist[1] = 0
    for i in range(vertex): 
        for j in range(len(edge_list)):
            cur_v, next_v, cur_cost = edge_list[j]
            if dist[next_v] > dist[cur_v] + cur_cost:
                dist[next_v] = dist[cur_v] + cur_cost
                # 만일 꼭지점 개수만큼 돌고 있다면..? 음의 사이클 발생.
                # why? 최단 경로는 최악의 경우 V-1개라고 가정한다.
                # 즉, 거리가 갱신되었는데 V번째 돌고 있다면 어딘가 음의 사이클 발생으로 볼 수 있다.!
                # 왜냐면, 양의 거리였다면 갔던데를 어디 뭐 다시 가서 사이클이 생길리가 없음 V-1 확정
                # 음일 사이클이 있으면 V-1 돌고도 갱신될 만한 여지가 있어서 또 갱신 되었다를 의미함.
                if i == vertex - 1:
                    return "YES"
    return "NO"
            
t_case = int(input())
for _ in range(t_case):
    vertex, road, hole = map(int, input().split())
    edge_list = []
    
    # 양방향 양의 거리
    for _ in range(road):
        start, end, time = map(int, input().split())
        edge_list.append([start, end, time])
        edge_list.append([end, start, time])
    # 단반향 음의 거리
    for _ in range(hole):
        start, end, time = map(int, input().split())
        edge_list.append([start, end, -time])
    
    # bellman-ford
    dist = [1e12] * (vertex + 1)
    print(bellman_ford(vertex, edge_list, dist))