[ 백준 / 11657 ] 타임머신 (Python)

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

 

난이도 : 골드 4 
알고리즘 유형 : 벨만포드 
풀이 시간 : 19분 

문제 풀이 

문제의 주 목적은 1번 정점에서 나머지 모든 정점을 가는 데 걸리는 시간을 구하는 문제이다. 그치만 문제에서 음수 사이클이 존재하기 때문에, 우리는 다익스트라 알고리즘 대신 벨만포드 알고리즘을 사용할 것이다.

 

벨만포드 알고리즘이란 ? 모든 정점과 엣지를 탐색하여 최소 거리로 업데이트해주기 위한 알고리즘이다. 다익스트라 알고리즘과 차이점이라면, 다익스트라 알고리즘은 최소 거리를 찾기 위해 그리디하게 값을 업데이트하지만, 벨만포드 알고리즘은 모든 정점과 간선을 다 방문해본다는 점이다. 

다익스트라 알고리즘의 시간복잡도는 $O(V + E)$이고, 벨만포드 알고리즘의 시간복잡도는 $O(VE)$로 복잡도 측면에서는 떨어지지만, 대신 음수 사이클을 확인할 수 있다는 것이 강점이다.

 

벨만포드 알고리즘에서 주의해야 할 부분이라면, 음수 사이클이 형성되는 부분이다. 

2번 → 3번 → 4번 간선 이동 시 음수 사이클이 형성된다.다

다음과 같은 경우, 2번 → 3번 → 4번 간선 이동 시 -2로 간선이 업데이트가 되고, 이 경우가 반복되는 것을 확인할 수 있다. 이런 경우를 방지하기 위해서 모든 간선을 탐색한 이후에도, 간선의 업데이트가 발생하면 종료하도록 예외 처리를 진행해주어야 한다.

 

코드

'''
c=0인 경우 : 순간이동을 하는 경우
c < 0 : 시간을 되돌아가는 경우

1번 도시에서 출발해서 나머지 도시로 가는 가장 빠른 시간을 구하는 프로그램 작성

풀이: 벨만-포드 알고리즘
시간을 오래 전으로 되돌릴 수 있는 경우 : 음수 간선 사이클이 존재하는 경우

벨만포드 알고리즘의 핵심 : 매 반복마다 모든 간선을 모두 확인한다.
'''

import sys
input = sys.stdin.readline

def bellman_ford(start):
    distance[start] = 0
    for i in range(n):
        # 매번 모든 간선에 대해서 확인
        for j in range(m):
            u, v, w = edges[j]
            # 현재 간선을 거쳐서 다른 노드로 이동하는 거리가 더 짧은 경우, 업데이트
            if distance[u] != int(1e9) and distance[u] + w < distance[v]:
                distance[v] = distance[u] + w
                # v번째 노드까지 방문했음에도 불구하고, 새로운 값이 갱신된다면 -> 음수사이클이 존재함
                if i == n - 1:
                    return False
    return True

n, m = map(int, input().split())
edges = [list(map(int, input().split())) for _ in range(m)]
distance = [int(1e9)] * (n + 1)

check_cycle = bellman_ford(1)
if not check_cycle:
    print(-1)
else:
    for u in range(2, n + 1):
        if distance[u] == int(1e9):
            print(-1)
        else:
            print(distance[u])

배운 점 

벨만포드 알고리즘을 푼 지 꽤 오래되어 가물가물해졌는데, 원리와 방법을 다시금 기억하게 해주었던 문제이다. 벨만포드 알고리즘의 기초이지만, 이를 심화해서 다양한 곳에 활용할 수 있을 것으로 생각된다.