[백준] 11657: 타임머신 - 벨먼-포드 알고리즘

문제이해

음의 간선이 있을 때 최단거리를 구하는 문제다.

계획

가중치가 있는 간선의 최단거리를 구하는 문제이므로 다익스트라를 생각할 수 있으나, 음의 간선이 있으므로 다음과 같은 경우가 생겨 다익스트라는 사용할 수 없다.

음의 간선이 있을 때 다음과 같은 경우가 있을 수 있다.

1. 모든 간선이 양수인 경우
2. 음수 간선이 있는 경우
   1. 음수 간선 순환이 있는 경우
   2. 음수 간선 순환이 없는 경우

만약 음수 간선 순환이 있는 경우, 그 사이클을 지나는 모든 노드들의 최단거리가 무한히 음수로 갱신된다.

따라서, 벨만-포드 알고리즘을 이용하면, 이런 경우들을 고려하여 최단거리를 구할 수 있다.

벨만-포드 알고리즘

벨만-포드 알고리즘은 다익스트라와 유사하다. 다른 점은 다익스트라는 조건에 맞는 몇몇 간선만 탐색한다면, 벨만-포드 알고리즘은 모든 간선을 다 탐색한다.

벨만-포드 알고리즘의 방식은 다음과 같다.

1. 출발 노드 설정
2. 최단 거리 테이블 초기화
3. 다음의 과정을 n-1번 반복
   1. 전체 간선을 하나씩 확인
   2. 각 간선을 거쳐 다른 노드로 가는 비용을 계산하여 최단 거리 테이블을 갱신

만약 음수 사이클이 발생하는지 체크하고 싶다면 3번의 과정을 한 번 더 수행. 이때 최단거리 테이블이 갱신된다면 음수 간선 순환이 존재한다.

계획수행

import sys
from collections import deque

n, m = map(int, sys.stdin.readline().split())
edge = []
inf = m*10001
distance = [inf]*(n+1)

for _ in range(m):
    a, b, c = map(int, sys.stdin.readline().split())
    edge.append((a, b, c))

distance[1] = 0
for i in range(n):
    for a, b, c in edge:	#모든 간선 탐색
        cost = distance[a] + c
        if distance[a] != inf and distance[b] > cost:
            if i == n-1:	#다 탐색 했는데 추가로 탐색 할때도 줄어든다면 음의 사이클
                print(-1)	#따라서, -1출력 후 종료
                exit(0)
            distance[b] = cost

for i in distance[2:]:
    if i == inf:
        print(-1)
        continue
    print(i)

 

 

느낀점

처음에는 다익스트라로 풀으려고 했는데 음의 사이클 자체를 생각하지 못했다. 음의 거리의 간선이 있는 경우는 조심해야겠다.