Python 백준 알고리즘 11657 : 타임머신

https://www.acmicpc.net/problem/11657

11657번: 타임머신

 

# 11657 타임머신 벨만 포드 알고리즘

n, m = map(int, input().split())
edges = []
INF = int(1e9)
dist = [INF] * (n+1)

for _ in range(m):
  a, b, c = map(int, input().split())
  edges.append((a,b,c))

def bellman_ford(start):
  dist[start] = 0
  for i in range(n):
    for j in range(m):
      current_node = edges[j][0]
      next_node = edges[j][1]
      cost = edges[j][2]
      if dist[current_node] != INF and dist[next_node] > dist[current_node] + cost:
        dist[next_node] = dist[current_node] + cost
        if i == n-1:
          return True
  return False

negative_cycle = bellman_ford(1)

if negative_cycle:
  print(-1)
else:
  for i in range(2, n+1):
    if dist[i] == INF:
      print(-1)
    else:
      print(dist[i])

 

이 문제는 다익스트라 알고리즘을 사용해서 풀 수 없다. 간선의 비용이 단순 음수라면 상관없겠지만, 음수 간선의 순환이 포함되어 있을 수 있기 때문에 다익스트라 알고리즘 대신에 벨만 포드 알고리즘을 사용해서 문제를 풀어야 한다. 나는 벨만 포드 알고리즘에 대해 알지 못했어서 아래 영상을 참고했다.

 

https://youtu.be/Ppimbaxm8d8

 

이 알고리즘은 최단거리가 가장 짧은 노드만 확인하지 않고 모든 간선을 확인해야 하기 때문에 시간복잡도가 다익스트라 알고리즘보다 크다.