타임머신

위상정렬을 공부하다가 우연히 이 문제까지 흘러 들어왔다. 처음으로 SPFA, Bellman Ford알고리즘을 접했다. 다익스트라 알고리즘의 경우 간선의 가중치가 음수일 때는 사용할 수 없다. 하지만, 이 알고리즘들 같은 경우에는 간선의 가중치가 음수일 때도 사용할 수 있다는 장점을 가지고 있다. 주로 타임머신, 블랙홀과 같은 키워드와 함께 자주 등장한다고 한다.

Bellman Ford

다익스트라 알고리즘의 경우 방문하지 않은 점들 중에 거리가 가장 가까운 점을 우선적으로 방문해 나간다. 따라서, 간선의 가중치가 음수일 경우 문제가 생길 수 있다.

Bellman Ford 알고리즘의 경우에는 각 점들을 돌면서 모든 간선을 탐색한다. 이 과정을 n-1번 반복한다. 타임머신 문제의 경우 음의 가중치를 가지는 간선이 있다. 이 때문에, 순환구조가 생길 수 있는다. 순환구조가 있는지 없는지 판단하기 위해서 모든 점을 돌며 탐색하는 과정을 n-1번 반복한 후에, 한 번 더 탐색을 해서 이때 또 다시 업데이트 되는 노드가 있는지 확인한다. n번째 탐색에서 거리가 업데이트 되는 점이 있다면 순환구조가 존재한다는 뜻이다!

Bellman Ford Algorithm에 대한 설명은 다른 블로그를 통해 공부했다. 조금 더 익숙해졌을 때, 한 번 더 집중적으로 설명하는 포스팅을 할 예정이다.

CODE - Bellman Ford

import sys
read = sys.stdin.readline
inf = sys.maxsize

n, m = map(int, read().split())
bridge = list([] for _ in range(n+1))
for _ in range(m):
    a, b, c = map(int, read().split())
    bridge[a].append([b, c])

dp = list(inf for _ in range(n+1))
dp[1] = 0

# n번 반복!
for node in range(n):
    for i in range(1, n+1):
        for next, w in bridge[i]:
            #값이 초기 상태의 inf로 남아있는 점들에 대해서는
            if dp[i] != inf and dp[next] > w+dp[i]:
                dp[next] = w+dp[i]
                # n번째 반복에서도 업데이트 되는 node가 존재한다는 것은
                # 음의 사이클이 존재한다는 뜻이다.
                if node == n-1:
                    print(-1)
                    sys.exit()

for d in dp[2:]:
    print(d if d != inf else -1)


SPFA(Shortest Path Faster Algorithm)

위의 Bellman Ford Algorithm을 개선시킨 Algorithm이다. Bellman Ford에서는 정점들에서 이어지는 모든 간선을 업데이트 하지만, SPFA에서는 업데이트 된 정점으로부터 이어지는 간선에 대해서만 업데이트를 진행한다는 것이다.

또한, 업데이트 할 노드들을 deque를 활용해 관리한다. 이때, 업데이트 한 노드가 현재 deque에 속해있어 추가할 필요가 없는지, 혹은 deque에 추가해야 하는지 판단하기 위해 추가로 리스트를 사용한다. 발만 포드 알고리즘과 유사하게 해당 점을 n번 이상 방문하는 경우가 있는지 확인해 순환고리의 유무를 판단할 수 있다.

CODE - SPFA(Shortest Path Faster Algorithm)

from collections import deque
import sys
read = sys.stdin.readline
inf = sys.maxsize

n, m = map(int, read().split())
bridge = list([] for _ in range(n+1))
for _ in range(m):
    a, b, c = map(int, read().split())
    bridge[a].append((b, c))
# 1번 노드로 부터의 거리 저장
dp = list(inf for _ in range(n+1))
dp[1] = 0
# deque내에 점이 포함되어 있는지 검사 + 방문 횟수 검사
# 양수면 deque내에 포함
check = list(0 for _ in range(n+1))

point = deque([1])
check[1] = 1

while point:
    a = point.popleft()
    check[a] *= (-1)
    for i, w in bridge[a]:
        if dp[i] > dp[a]+w:
            dp[i] = dp[a]+w
            if check[i] <= 0:
                check[i] = check[i]*(-1)+1
                point.append(i)
                if check[i] >= n:
                    print(-1)
                    sys.exit()
for d in dp[2:]:
    print(d if d != inf else -1)


틀린 부분이 있을 수 있습니다. 피드백 주시면 고치도록 하겠습니다! 감사합니다.👍

[꼭 다시 풀어보기]