[ 백준 ][ 골드4 ] 11657번 - 타임머신 ( 파이썬 )

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

11657번: 타임머신

 

문제

---

 

코드

---

import sys
input = sys.stdin.readline

def belman_ford(start):
    dist[start] = 0
    for i in range(1,n+1):
        for j in range(m):
            now, next, weight = graph[j]
            if dist[now] != 1e9 and dist[next] > dist[now] + weight:
                dist[next] = dist[now] + weight
                if i == n: return True
    return False

n, m = map(int,input().split())
graph = []
dist = [1e9] * (n+1)
for _ in range(m):
    graph.append(list(map(int,input().split())))

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

 

풀이

---

11657번 타임머신 문제는 음수 간선을 포함하는 그래프에서 최단 거리를 구하는 문제이다.

해당 문제는 전형적인 벨만-포드 알고리즘 문제로써 다익스트라 알고리즘과 비슷해 보일 수 있다.

 

다익스트라 알고리즘과 벨만-포드 알고리즘은 다음과 같은 차이점이 존재한다.

	다익스트라	벨만-포드
목적	한 점에서 다른 모든 노드로 가는 최단 거리를 구한다.	한 점에서 다른 모든 노드로 가는 최단 거리를 구한다.
진행방식	매번 방문하지 않은 노드 중에서 최단 거리가 가장 짧은 노들르 선택한다.	매번 모든 간선을 확인하며 n번째 확인할 때도최단거리가 갱신된다면 음의 순환이 있음을 인지한다.
장점	빠른 속도로 최적의 해를 찾을 수 있다.	음의 순환을 탐지할 수 있다.
단점	음의 간선이 없어야 한다.	시간이 오래 걸린다.
시간복잡도	O(NlogN)  ->  우선순위 큐 사용시	O(NM)  ->  간선수 * 노드수

 

따라서 이 문제는 음의 간선이 있으므로 벨만-포트 알고리즘을 사용하여 해결한다.

• 최단 거리를 구하는 문제이므로 초기 거리는 모두 1e9(최대값)으로 저장한다.
• 단방향 그래프이므로 (출발점, 도착점, 비용) 순으로 그래프를 저장한다.
• 벨만-포드 알고리즘을 사용한다.
  • 시작점의 거리는 0으로 초기화한다.
  • 모든 간선을 확인하는 과정은 n-1번 반복한다.
  • n-1번 확인하면서 최단 거리 테이블을 매번 갱신한다.
  • 만약 음수간선의 순환이 발생하는지 확인하고 싶다면 모든 간선을 한 번 더 탐색하며 거리를 갱신해본다.
  • 여기서 최단 거리 테이블이 갱신된다면 음수 간선의 순환이 존재하는 것이다.
• 벨만-포드로 음수 간선 순환을 확인하고 없다면 거리 테이블을 돌며 거리를 출력한다.