[Baekjoon] 타임머신(python)

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

문제 접근

시작 노드에서 각 노드별로 최단경로를 구하는 문제이다.

 

최단경로를 구하는 알고리즘은 다익스트라와 벨만포드가 있다.

 

이 문제는 Edge의 음수 가중치가 존재하므로 다익스트라를 이용해서 최단경로를 구하면 제대로된 거리를 구할 수 없다.

 

따라서 음수 가중치가 있어도 최적해를 찾을 수 있는 벨만포드 알고리즘을 이용해서 문제를 해결해야 한다.

---

풀이 과정

벨만포드 알고리즘 순서

1. 출발 노드 설정
2. dist 배열 초기화
3. 모든 간선에 대해 각 간선을 거쳐 다른 노드로 가는 최단 거리 갱신 -> (정점의 갯수 - 1)번 수행

3번이 끝난 후에도 최단 거리가 갱신된다면 음수 사이클이 존재하는 것이다.

 

이 과정을 코드로 구현해보자.

def bellmanford():
    for i in range(N):
        for e in edge:
            cur_node, next_node, cost = e

            if dist[cur_node] != INF and dist[next_node] > dist[cur_node] + cost:
                dist[next_node] = dist[cur_node] + cost

                if i == N - 1:
                    return True
    return False

(정점의 갯수 - 1)번만 수행하는 이유는 시작 노드에서 각 노드까지의 최단 경로를 구할 때 최대로 거칠 수 있는 Edge 갯수가 정점의 갯수 - 1이기 때문이다.

---

정답 코드

"""
    백준 11657번 타임머신
"""

import sys

N, M = list(map(int, sys.stdin.readline().split()))
edge = []
INF = int(1e9)

dist = [INF] * (N + 1)
dist[1] = 0

for _ in range(M):
    edge.append(list(map(int, sys.stdin.readline().split())))


def bellmanford():
    for i in range(N):
        for e in edge:
            cur_node, next_node, cost = e

            if dist[cur_node] != INF and dist[next_node] > dist[cur_node] + cost:
                dist[next_node] = dist[cur_node] + cost

                if i == N - 1:
                    return True
    return False


is_negative = bellmanford()

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