[백준] 11657번 - 타임머신

---

문제 분석

시작점 및 다른 노드와 관련된 최단 거리를 구하는 문제지만, 특이한 점은 에지에 해당하는 이동하는 시간이 양수가 아닌 0 또는 음수가 가능하다는 점이다. 이렇게 시작점에서 다른 노드와 관련된 최단 거리를 구하는데, 에지가 음수가 가능할 때는 벨만-포드 알고리즘을 사용하면 된다.
다음은 벨만 포드 알고리즘과 관련된 원리에 대한 설명이다.

---

벨만-포드 알고리즘은 다음 3가지 단계의 원리로 동작한다.

💡 1단계 : `**에지 리스트**로 그래프를 구현하고 **최단 경로 리스트** 초기화하기`

: 주어진 경로를 에지 리스트의 형태로 설계하고, 최단 경로 리스트를 초기화 한다.

이때, 최단 경로 리스트에서 시작 노드의 번호에 해당하는 인덱스를 가진 곳의 값은 0, 나머지 값들은 sys.maxsize로 초기화 한다.

---

💡 2단계 : `모든 에지를 확인해 **정답 리스트** 업데이트 하기`

: 노드의 개수가 N이라고 할 때, N-1번 에지 리스트 전체를 탐색하면서, 최단 경로 리스트를 업데이트 하는 과정이 필요하다.

최단 경로 리스트(minRoute)를 업데이트 하는 조건은 다음과 같다. (s,e,w ⇒ 시작, 끝 가중치)

minRoute[s] != sys.maxsize and minRoute[e] > minRoute[s] + w

❗위의 두 조건에서 첫 번째 조건에 주의 해야 한다.

첫 번째 조건의 의미는 접근한 적이 있는 노드인지 판별하는 것으로, 음수 가중치가 존재하기 때문에, 다익스트라 방법과는 달리 이러한 조건이 필요하다.

💡 예를 들어, 마지막 상황에서 두 노드가 모두 sys.maxsize값을 가진다고 했을 때, A노드에서 B노드로 가는 가중치가 음수라고 하면, 두 노드 모두 접근이 불가능 한데, B노드가 업데이트 상황이 발생하고 이는 success를 False로 만들게 되므로, 해당 조건 (minRoute[s] ≠ sys.maxsize) 은 음수 가중치를 가진 곳에서 반드시 필요하다!

---

💡 3단계 : `음수 사이클 유무 확인하기`

: 마지막으로 에지 리스트를 처음부터 끝까지 돌면서,

2단계에서 사용한 두 조건에 따라 최단 경로 리스트의 변화가 있는지 살펴본다.

만약 변화가 있다면, 음수 사이클이 존재한다는 것으로 파악할 수 있으며, 이러한 경우에는 초기 시작노드로 부터 각각의 노드까지 가는 최단 경로를 없다고 볼 수 있다.

---

소스 코드

# 타임머신

import sys
input = sys.stdin.readline

N, M = map(int, input().split())
arr = []
minRoute = [sys.maxsize] * (N + 1)
minRoute[1] = 0

for _ in range(M):
    s, e, w = map(int, input().split())
    arr.append((s, e, w))

for _ in range(N - 1):
    for s, e, w in arr:
        if minRoute[s] != sys.maxsize and minRoute[e] > minRoute[s] + w:
            minRoute[e] = minRoute[s] + w

success = True

for s, e, w in arr:
    if minRoute[s] != sys.maxsize and minRoute[e] > minRoute[s] + w:
        success = False

if success:
    for value in minRoute[2:]:
        if value == sys.maxsize:
            print(-1)
        else:
            print(value)
else:
    print(-1)