[백준] 웜홀 : 1865 Python

이 문제를 봤을 때, 플로이드 와샬로 풀 수 있을까 고민했지만 tc의 개수가 5개, N의 크기가 500인 것을 보고 플로이드와 샬을 포기하고, 음의 가중치라는 점에서 벨만 포드 알고리즘을 시도했다.

벨만 포드 알고리즘이 익숙지 않아 많이 헤맸던 문제이지만, 이 문제 덕에 벨만 포드 알고리즘을 한번 더 정리할 수 있었다.

벨만 포드 알고리즘은 다익스트라와 같이 최단 경로 문제를 푸는 알고리즘이지만, 차이점은 변과 변 사이에서 음의 가중치를 가질 수 있다는 점이고 바로 이 점이 훨씬 더 빠른 다익스트라보다 벨만 포드 알고리즘을 사용하는 이유이다.

왜 다익스트라는 음의 가중치를 가지지 못할까? 음의 가중치가 있는 경우  음의 순환(계속 가중치가 최솟값으로 갱신되는 경우)이 있다. 다익스트라는 가중치의 합을 최솟값으로 갱신해나가는데 이 경우 계속 최솟값으로 값을 경신해나가며 알고리즘을 끝을 내지 못할 것이다. 

그렇다면 벨만포드 알고리즘은 어떻게 음의 사이클이 존재하여도 최적의 값을 구하고 끝낼 것인가?  그 이유는 최단거리를  찾는 과정을 N-1번만 가지기 때문이다. 

왜 N-1번 탐색을 하면 최적거리알고리즘을 끝내도 되는 것일까? N개의 노드가 존재한다고 했을 때, N-1번의 최단거리 탐색을 한다면 N-1개의 노드를 거쳐갔을 때의 최소 가중치를 알 수 있기 때문이다. (최단 거리인데 N개의 노드를 거친다는 것은 오류가 있다.)

즉, 벨만포드 알고리즘은 현재 위치를 기준으로 모든 루트를 N-1번 확인하며 루트가 N-1개의 이하 가지는 최단거리를 찾는 알고리즘인 것이다. 

이제 문제로 들어가보면 이 문제는 음의 사이클이 존재하는지 확인하는 문제이고 벨만 포드 알고리즘의 특징을 활용해서 푸는 문제였다. N-1번 최단경로를 찾는 벨만 포드 알고리즘에 특징을 활용해서 한번 더 시행해서 최단경로가 있다면 음의 사이클이 있다고 생각하면 되는 것이다.

또 주의할점은 이 문제는 시작 위치가 정해져 있지 않다. 하지만 벨만 포드 알고리즘을 잘 이해하고 활용한다면 문제 되지 않는다. 벨만 포드 알고리즘은 원래 목적은 한 위치에서 다른 위치까지 최단거리를 찾는 것이기 때문에, 그 시점에서 시작 위치에서 연결되어 있지 않는 점은 고려하지 않는다. 결국 자신과 상관없는 곳에 노드들이 음의 관계를 가지는 것은 찾기 않게 된다.

즉, 시작점이 어디든 모든 곳의 연결관계를 고려해서 시행하면 자연스럽게 음의 상관관계를 모두 찾을 수 있다. 그리고 이를 위해서는 inf를 사용하면 안된다(int+상수 = inf)이기 때문에 자신과 상관없는 노드는 갱신된다고 생각하지 않기 때문이다.

이제 이를 코드로 나타내면 아래와 같다.

from sys import stdin

input = stdin.readline

def bf():
    # inf를 사용하지 않고 임의의 큰 수 사용
    D = [200000000] * (N+1)
    # 어느 점을 기준으로 해도 상관없음
    D[1] = 0

    # N번 검사 
    for i in range(N):
        for rou in route:
            start, goal, time = rou
            if D[goal] > D[start] + time:
                D[goal] = D[start] + time
                # N번 시행시 갱신된다면, 음의 가중치 판단.
                if i == N-1:
                    return 'YES'
    return 'NO'


# 변수 입력
TC = int(input())

for _ in range(TC):
    N, M, W = map(int,input().split())
    route = []
    for _ in range(M):
        a, b, t = map(int,input().split())
        route.append([a,b,t])
        route.append([b,a,t])

    for _ in range(W):
        s, e, t = map(int,input().split())
        route.append([s,e,-t])


    print(bf())

이 문제를 풀면서 내가 한번 더 벨만포드알고리즘에 대해 정리한 내용이기 때문에 틀린 내용이 있을 수 있다.  이 문제를 푸는 힌트는 아래의 게시판에 정리해서 올려주신 jh05013님의 내용 덕에 얻을 수 있었다.

https://www.acmicpc.net/board/view/72995

글 읽기 - 풀이 및 논란 완전히 정리합니다.

 

문제 출처 : https://www.acmicpc.net/problem/1865

1865번: 웜홀