백준 11657번: 타임머신

✔ 풀이를 위한 아이디어

• 그래프 (Graph) 이론
• 벨만-포드 알고리즘 (Bellman-Ford’s algorithm)
  
  

✔ 알고리즘 설명

벨만-포드 알고리즘을 공부한 뒤에 코드를 짜보았다.
https://www.youtube.com/watch?v=Ppimbaxm8d8 를 참조하였다.

• 벨만-포드 알고리즘의 특징

1. 다익스트라 알고리즘과 같이, 한 지점에서 다른 모든 지점으로의 최단거리를 구하는 알고리즘이다.
2. 가중치가 음수인 경우 사용한다.
3. 음수 사이클의 존재 여부를 판단할 수 있다.

• 다익스트라 알고리즘과의 비교

1. 다익스트라 알고리즘은 최단거리가 가장 짦은 지점부터 체크 해나가므로, 한번 체크한 지점은 다시 확인하지 않는다.
2. 반면, 벨만-포드 알고리즘은 모든 '간선'을 확인하는 과정을 거치며, 해당 과정을 V-1번 반복하여 수행하므로 가중치가 음수인 경우도 고려할 수 있게 된다.
3. 다익스트라 알고리즘의 시간복잡도는 O(V^2) 이다. 이는 모든 지점 (V) 에서 반복하고, 매번 길이가 V인 테이블에서 최단거리가 가장 짧은 지점을 선택 (V) 하기 때문이다.
4. Heap을 사용하는 다익스트라 알고리즘의 경우는 O(ElogV) 이다. 어짜피 지점에 딸린 간선의 수만큼 반복하므로 (E) 이고, Heap을 사용하면 (logV) 만에 최단거리가 가장 짧은 지점을 선택할 수 있기 때문이다.
5. 벨만-포드 알고리즘은 (V-1) 번 반복하여 모든 간선을 고려 (E) 하므로 시간복잡도가 O(VE) 이다.

✔ 전체 코드

import sys
INF = float('inf')

N, M = map(int, sys.stdin.readline().split())

graph = {}  # 전체 graph는 dictionary임
for i in range(N):
    graph[i+1] = []  # 각 지점마다 각자의 array를 가지고 있음
for _ in range(M):
    A, B, C = map(int, sys.stdin.readline().split())
    graph[A].append([B, C])  # index 0이 지점, index 1이 비용인 array를 넣어줌

dist = [INF]*(N+1)


def bellman_ford(start):
    dist[start] = 0
    for i in range(N):
        for a in range(1, N+1):
            for b, c in graph[a]:
                if dist[b] > dist[a] + c:
                    dist[b] = dist[a] + c
                    if i == N-1:
                        return True
    return False


negativeCycle = bellman_ford(1)
if negativeCycle:
    print("-1")
else:
    for i in range(2, N+1):
        if dist[i] == INF:
            print("-1")
        else:
            print(dist[i])

• 벨만-포드 알고리즘의 흐름

1. 출발 노드를 설정하고, 최단거리 테이블을 초기화.

dist = [INF]*(N+1)
dist[start] = 0

2. 전체 간선 E를 하나씩 확인하며, 각 간선을 거쳐 다른 노드로 가는 비용을 계산해 테이블 갱신.
   그리고 이 과정을 N-1번 반복.

for i in range(N-1):  # 한번에 특정지어버리는 다익스트라와 다르게 N-1번 반복
    # 밑의 2중 for문의 최대 반복 횟수가 간선의 개수와 같으므로 시간복잡도 O(E)
    for a in range(1, N+1):  
        for b, c in graph[a]:  # (각 지점에서 연결된 간선의 개수만큼 반복)
            if dist[b] > dist[a] + c:
                dist[b] = dist[a] + c

3. 음수 간선 순환이 발생하는지 체크하기 위해 N-1번보다 한번 더 반복.
   이때 최단거리 테이블이 갱신된다면, 음수 간선 순환이 존재하는 것으로 판단.

for i in range(N):  # N-1 -> N
    for a in range(1, N+1):
        for b, c in graph[a]:
            if dist[b] > dist[a] + c:
                dist[b] = dist[a] + c
                if i == N-1:  # N번째에 갱신되면 순환이 존재하는 것으로 판단
                    return True
return False   # 그렇지 않으면 존재 안하는 것으로 판단

벨만-포드 알고리즘은 N-1번 반복해줘야 정상적으로 동작한다는 것을 기억하자!