1 minute read

문제

접근 방법

웜홀은 어떻게 보면 음의 가중치를 가진 간선으로 볼 수 있다. 여기서 문제가 요구하는 것은 음의 cycle이 존재하는지 묻는 것으로 볼 수 있다. 음의 가중치를 가진 간선을 다뤄야 하므로 벨만포드 알고리즘을 생각해냈다. 벨만 포드 코드를 보면

# 시작점에 대해서 mid_node을 거쳐서 end_node까지의 거리와 시작점에서 직접 end_node까지 가는 거리를 비교해서 
#n-1 개의 node 까지의 최소 거리를 update. 시작점과 시작점 사이의 거리는 무조건 0이므로 n-1번만 반복.

for _ in range(n-1):
  for mid_node in range(n):
    for end_node, weight in graph[mid_node]:
      new_dist = distances[mid_node] + weight
      if new_dist < distances[end_node]:
        distances[end_node] = new_dist
# 마지막 iteration은 음의 사이클 존재 여부를 판단하는 코드이다. 
#한번 더 수행했을 때, 시작점에서 다른 노드까지의 거리가 줄어들었다면 
#그것은 음의 사이클이 존재한다는 의미.
for mid_node in range(n):
  for end_node, weight in graph[mid_node]:
    if distances[end_node] < distances[mid_node] + weight:
      return "음의 사이클 존재"

이 문제는 시작점이 주어져있지 않지만 그냥 시작점과 시작점의 사이의 거리를 int(1e9)로 보고 벨만포드 알고리즘을 사용하는 것과 같다.

정답 코드

import sys
input = sys.stdin.readline

TC = int(input())

for _ in range(TC):
  n,m,w = map(int, input().split())
  graph = [[] for _ in range(n+1)]
  for _ in range(m):
    s,e,t = map(int, input().split())
    graph[s].append((e,t))
    graph[e].append((s,t))
  for _ in range(w):
    s,e,t = map(int, input().split())
    graph[s].append((e,-t))

  distances = [int(1e9)]*(n+1)
  distances[1] = 0
  cycle = False
  # 최소 거리 update
  for _ in range(n-1):
    for mid_node in range(1,n+1):
      for end_node, weight in graph[mid_node]:
        new_dist = weight + distances[mid_node]
        if new_dist < distances[end_node]:
          distances[end_node] = new_dist

  # 음의 사이클 존재 여부 확인
  for mid_node in range(1,n+1):
    for end_node, weight in graph[mid_node]:
      new_dist = weight + distances[mid_node]
      if new_dist < distances[end_node]:
        cycle = True
        break
        
  if cycle:
    print("YES")
  else:
    print("NO")

느낀 점

벨만 포드의 코드를 더 깊게 이해하게 해준 문제이다. 알고리즘을 외우는 것이 아니라 각 부분 별 역할을 명확하게 이해한 것이 도움이 됐다.

You May Also Enjoy