백준 1865번: 웜홀

✔ 풀이를 위한 아이디어

• 그래프 (Graph) 이론
• 벨만-포드 알고리즘 (Bellman-Ford’s algorithm)
  
  

✔ 개요

• 이 문제의 핵심은 '음수 사이클의 존재 여부'를 판단하는 것인데, 이전에 풀었던 '타임머신' 문제의 코드를 조금 변형해줘야 맞출 수 있었다.
  https://velog.io/@dlehdtjq00/백준-11657번-타임머신

✔ 전체 코드

import sys

def bellman_ford():
    for i in range(N):
        for a in range(1, N+1):
            for b, c in graph[a]:
                if dist[b] > dist[a] + c:
                    dist[b] = dist[a] + c
                    if i == N-1:
                        return True
    return False


TC = int(input())
for _ in range(TC):
    N, M, W = map(int, sys.stdin.readline().split())
    graph = {} 
    for i in range(N):
        graph[i+1] = []
    for _ in range(M):
        A, B, C = map(int, sys.stdin.readline().split())
        graph[A].append([B, C])
        graph[B].append([A, C])  # 도로는 양방향으로 넣어줌
    for _ in range(W):
        A, B, C = map(int, sys.stdin.readline().split())
        graph[A].append([B, -1*C])  # 웜홀의 경우 시간이 줄어딜기 때문에 -1을 곱해서 넣어줌

    dist = [0]*(N+1)  # 테이블을 INF가 아닌 0으로 초기화하여, 모든 지점에서 시작되도록
    negativeCycle = bellman_ford()
    if negativeCycle:
        print("YES")
    else:
        print("NO")

• 중요한 수정 포인트

1. 이 문제에서 가장 크게 고민해야할 것은, '시작점을 어디로 지정해야할까' 이다. 기존처럼 최단거리 테이블을 INF로 초기화하고 시작점만을 0으로 설정한다면, 값이 INF인 (방문하지 않은) 정점에 대해서는 갱신이 이루어지지 않고, 결과적으로 시작점에서 도달할 수 없는 음수 사이클은 못찾기 때문에 틀리게 된다.

2. 따라서, 모든 지점을 시작점으로 하여 음수 사이클이 하나라도 존재하는지를 찾아내야한다. 이를 위해 처음에 나는 아래와 같이 for문을 돌리며 각 지점마다 벨만-포드 알고리즘을 돌렸다. 그러나 이 방식은 시간복잡도가 O(V^2E)로 매우 높으므로, 시간초과를 받게 되었다.

for i in range(1, N+1):
    negativeCycle = bellman_ford(i)
    if negativeCycle:
        print("YES")
        break
    elif not negativeCycle and i == N:
        print("NO")

3. 이후, 내가 택한 방법은 모든 지점에서 '동시에' 시작되도록 하는 방식이었다. 이를 위해서 테이블을 INF가 아닌 0으로만 채우고, 벨만-포드를 돌렸다.
   이렇게 하면, 최단경로가 0보다 큰 경우를 정확히 구할 수 없지만, 어짜피 음수 사이클을 찾는 것이 목적이므로 정답을 맞추는 데에는 문제가 없다.
   이를 잘 정리해둔 글이다 -> https://www.acmicpc.net/board/view/72995

코드의 오타를 제대로 확인 안하고, 급하게 제출했다가 에러를 잔뜩 받았다. 앞으로는 꼭 확인하고 제출하자!