[백준] 1865번: 웜홀

문제

백준 - 1865번: 웜홀

분석

N개의 지점, 무방향인 도로 M개와 방향이 있는 웜홀 W에 대한 정보가 주어진다.
한 지점에서 출발해서 원래 지점으로 돌아왔을 때, 시간이 더 적어지는 경우가 있는지 판별하는 문제이다.

웜홀에서의 가중치는 음수로 생각해야한다.
이제껏 양수 가중치에서 최소비용을 생각했는데, 음수가 고려되기 위해서는 벨만 포드라는 알고리즘을 배워야한다.

1. 최단거리 배열을 초기화한다.
2. 전체 간선을 확인하는 작업을 n-1 번 반복한다.
   2-1. 최단거리 배열을 갱신한다.
3. 마지막에 한 번 더 작업했을 때도 최단거리 배열이 갱신되면 음수 사이클이 존재하는 것이다.

음수 사이클이 존재하면 YES, 없으면 NO를 출력한다.

코드

해결언어 : Python

import sys
input = sys.stdin.readline

INF = sys.maxsize

def bf():
    dist = [INF]*(n+1)
    for i in range(n):
        for now, nxt, d in edges:
            if dist[nxt] > dist[now] + d:
                dist[nxt] = dist[now] + d
                if i == n-1:
                    return True
    return False

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))
    if bf():
        print('YES')
    else:
        print('NO')

끝으로..

오늘은 벨만 포드 알고리즘에 대해 배웠다. 벨만 포드는 모든 간선을 확인하기 때문에 시간이 오래걸리는 대신 음수간선 사이클을 탐지할 수 있는 장점이 있다.
음수가 들어간 그래프에서의 최소 비용 문제에 대해 다뤄볼 수 있어 좋았다.