[백준] 11657번 타임머신 | 벨만 포드 알고리즘 파이썬 Python

백준 11657번 타임머신 문제는 최단거리 알고리즘 중에서 벨만 포드를 써야 한다.

문제에 버스 시간 C가 양수가 아닌 경우가 있기 때문에 다익스트라 알고리즘은 사용할 수 없다.

 

다익스트라는 가중치가 양수일 때만, 음수가 있는 경우는 벨만 포드를 쓴다.

 

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

 

문제

 

 

 

설명

 

최단 거리 알고리즘(다익스트라, 벨만포드, 플로이드)의 총정리는 알고리즘 카테고리에서 다뤘으니

여기선 문제에 대한 분석만 하겠다.

 

1. 최단 거리 리스트는 출발 노드만 0, 나머지는 무한대로 초기화한다.

dist = [float('inf')] * (n+1)
dist[1] = 0

 

 

2. 벨만 포드는 엣지가 중심이므로 엣지에 대한 그래프를 만든다.

graph.append([start,end,time])

 

 

3. 노드가 n개인 경우 엣지의 최대 갯수는 n-1개이다.

출발 노드가 무한대가 아니고 D[end] 가 D[start] + time 보다 작을 때 리스트 값을 업데이트한다.

for _ in range(n-1):
    for start, end, time in graph:
        if dist[start] != float('inf') and dist[end] > dist[start] + time:
            dist[end] = dist[start] + time

 

 

4. n-1번 업데이트한 결과와 n번째 결과값을 비교해서 업데이트가 일어나면 음수사이클이 존재한다는 뜻이다.

즉 최단거리를 구할 수 없으므로 -1을 출력한다.

for start, end, time in graph:
    if dist[end] > dist[start] + time:
        print(-1)

 

 

코드

import sys
input = sys.stdin.readline

n, m = map(int, input().split())
graph = []
dist = [float('inf')] * (n+1)
dist[1] = 0

# 엣지 데이터 저장
for _ in range(m):
    s, e, t = map(int, input().split())
    graph.append([s,e,t])

# n-1번 탐색
for _ in range(n-1):
    for start, end, time in graph:
        if dist[start] != float('inf') and dist[end] > dist[start] + time:
            dist[end] = dist[start] + time

# 음수사이클 확인
for s, e, t in graph:
    if dist[e] > dist[s] + t:
        print(-1)
        sys.exit()

for i in range(2, n+1):
    if dist[i] != float('inf'):
        print(dist[i])
    else:
        print('-1')