[Python Algorithm] 백준 웜홀 - 1865

풀이 과정

이전에 풀었던 타임머신 문제와 유사하게 벨만-포드 알고리즘을 사용하면 간단하게 해결할 수 있는 문제이다.

단, 주의할 점은 이 문제는 시작지점이 주어지지 않고, 단순히 음의 순환이 있는지 없는지를 판별하는 문제이므로 거리 배열을 초기화 해줄때 INF(무한대)로 초기화를 해주면 풀리지 않는다.

이 부분 때문에 여러번 도전을 해서 겨우 알아냈다...

최종 코드

T = int(input())
INF = 2147483647

def bell_ford(distance, graph, N):
  for i in range(N):
    for j in range(1, N + 1, 1):
      for vertex, value in graph[j]:
        if distance[vertex] > distance[j] + value:
          distance[vertex] = distance[j] + value
          if i == N - 1:
            return True
  return False

for _ in range(T):
  N,M,W = map(int, input().split(' '))
  distance = [INF for _ in range(N + 1)]
  graph = [[] for _ in range(N + 1)]

  for _ in range(M):
    S, E, V = map(int, input().split(' '))
    graph[S].append((E, V))
    graph[E].append((S, V))

  for _ in range(W):
    S, E, V = map(int, input().split(' '))
    graph[S].append((E, -V))

  print("YES") if bell_ford(distance, graph, N) else print("NO")

결과

Link

웜홀 문제 출처
GitHub 코드