[BOJ, Python] 1865번_웜홀

백준 1865번

단순 최단 경로 문제라고 생각했는데 한 가지 다른 점이 있었다.
웜홀의 경우에는 가중치가 음수인 것이다.
다익스트라 알고리즘을 사용해서 풀어보력 했지만 우선 순위 큐의 기준이 될 가중치가 웜홀의 경우 항상 음수이기 때문에 사용할 수 없었다.

결론적으로 이 문제는 벨만-포드(Bellman-Ford's) 알고리즘 문제였다.

벨만-포드(Bellman-Ford's) 알고리즘
음의 가중치를 허용하는 그래프에서 출발 노드로부터 다른 모든 노드까지의 최단 경로를 찾는 알고리즘이다. 다익스트라 알고리즘과 달리, Bellman-Ford는 그래프에 음의 가중치가 있어도 정확한 최단 경로를 찾을 수 있다. 또한, 이 알고리즘은 음수 사이클(노드의 합이 음수인 사이클)을 감지할 수 있다.

Bellman-Ford 알고리즘 동작 원리

• 초기화: 출발 노드의 거리를 0으로 설정하고, 다른 모든 노드의 거리를 무한대로 설정합니다.
• 간선 완화: 그래프의 모든 간선을 N-1번 반복하여 검사합니다. 여기서 N은 그래프의 노드 수입니다.
  - 각 반복마다 모든 간선 (u, v)에 대해, dist[v] > dist[u] + weight(u, v)이면, dist[v] = dist[u] + weight(u, v)로 갱신합니다. 이 과정을 N-1번 반복하면, 음수 사이클이 없는 경우 모든 노드에 대한 최단 경로가 안정화됩니다.
• 음수 사이클 체크: 모든 간선을 한 번 더 검사하여, dist[v] > dist[u] + weight(u, v)이면 음수 사이클이 존재한다고 보고합니다.

다만 이 문제는 Negative Cycle가 존재하는지만 확인하면 된다.

전체 풀이

import sys
input = lambda: sys.stdin.readline().rstrip()

INF = int(1e9)

def bf():
    for i in range(N):
        for j in range(2*M+W):
            curNode, nextNode, cost = edges[j]
            
            if distance[nextNode] > distance[curNode] + cost:
                distance[nextNode] = distance[curNode] + cost
                if i == N-1: # N번째 반복에서 갱신되는 값이 있다면 Negative Cycle 존재
                    return True
    return False


TC = int(input())
for _ in range(TC):
    N, M, W = map(int, input().split()) # 지점, 도로, 웜홀 개수
    edges = []
    distance = [INF]*(N+1)
    for _ in range(M):      
        S,E,T = map(int, input().split()) # 지점1, 지점2, 걸리는 시간
        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")

풀이는 매우 간단하다 N-1번 간선 완화를 진행하고 N번째에서 최단 경로가 갱신된다면 Negative Cycle이 존재하는 것이기 때문에 "YES"를 출력하면 된다.

일반적인 벨만-포드 문제와 다른 점이 존재해서 여러 논란과 헷갈리는 점이 존재하는 문제이다.
자세한 사항은 jh05013님이 정리하신 글을 확인해보자.

결과