[Python Algorithm] 백준 타임머신 - 11657

풀이 과정

다익스트라 알고리즘은 간선의 가중치가 양수인 경우만 해결할 수 있는 반면 벨만-포드 알고리즘은 가중치가 음수인 경우도 고려한 알고리즘이다.
해당 문제는 가중치가 음수인 경우도 나오기 때문에 다익스트라 알고리즘이 아닌 벨만-포드 알고리즘을 사용해야한다.
벨만-포드 알고리즘에 대한 공부는 아래 블로그를 참고하였다.
벨만-포드 알고리즘

최종 코드

INF = float('INF')
N, M = map(int, input().split(' '))

graph = [[] for _ in range(N + 1)]
distance = [INF for _ in range(N + 1)]

for _ in range(M):
  start, end, value = map(int, input().split(' '))
  graph[start].append((value, end))

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

if bell_ford():
  print(-1)
else:
  for i in range(2, len(distance)):
    print(distance[i]) if distance[i] != INF else print(-1)

결과

Link

타임머신 문제 출처
GitHub 코드