벨만-포드: 백준 1865 오답노트

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

Bellman-Ford 알고리즘은 최단 경로를 찾는 알고리즘 중 하나로, 음수 가중치가 포함된 그래프에서도 동작한다. 특히, 음수 사이클(negative cycle) 이 존재하는지를 판별하는 데 유용하다. 이번 글에서는 Bellman-Ford 알고리즘의 원리를 깊이 있게 설명하고, 코드 실행 과정을 표로 정리하여 직관적으로 이해할 수 있도록 한다.

---

1. Bellman-Ford 알고리즘의 핵심 원리

1. 최단 거리 배열(dist)을 활용해 거리 갱신

   • 모든 노드까지의 최단 거리를 저장하는 dist 배열을 사용한다.
   • 일반적으로 최단 경로를 구할 때는 dist를 무한대로 초기화하지만, 이번 문제에서는 음수 사이클을 판별하기 위해 모든 값을 0으로 초기화한다.

2. n-1번 반복하는 이유

   • 최단 경로의 간선 개수는 최대 n-1개이므로, n-1번 반복하면 모든 노드의 최단 거리 값이 확정된다.

3. 음수 사이클 판별을 위한 추가 반복

   • n-1번 반복 후 한 번 더 반복했을 때 최단 거리가 갱신되면, 해당 노드는 음수 사이클에 포함되어 있다는 의미이다.
   • 이를 이용해 음수 사이클이 있는지 확인한다.

---

2. 코드 분석 및 실행 과정

🔹 코드 설명

import sys

def bellman_ford(n, edges):
    # 모든 정점의 거리를 0으로 초기화 (음수 사이클 판별 목적)
    dist = [0] * (n + 1)

    # n-1번 반복하여 최단 경로 찾기
    for _ in range(n - 1):
        for s, e, t in edges:
            if dist[s] + t < dist[e]:
                dist[e] = dist[s] + t

    # 음수 사이클 존재 여부 확인
    for s, e, t in edges:
        if dist[s] + t < dist[e]:
            return "YES"

    return "NO"

def main():
    # 테스트 케이스 수 입력
    tc = int(sys.stdin.readline())

    for _ in range(tc):
        n, m, w = map(int, sys.stdin.readline().split())
        edges = []
        
        # 도로 정보 입력 (양방향)
        for _ in range(m):
            s, e, t = map(int, sys.stdin.readline().split())
            edges.append((s, e, t))
            edges.append((e, s, t))
        
        # 웜홀 정보 입력 (단방향, 음수 가중치)
        for _ in range(w):
            s, e, t = map(int, sys.stdin.readline().split())
            edges.append((s, e, -t))
        
        print(bellman_ford(n, edges))

if __name__ == "__main__":
    main()

🔹 dist[e]의 의미

dist[e]는 어떤 노드에서 출발했는지에 관계없이, 현재까지 갱신된 e번 노드까지의 최단 거리(시간) 를 나타낸다.

if dist[s] + t < dist[e]:
    dist[e] = dist[s] + t

위 코드에서 dist[s] + t가 dist[e]보다 작다면, dist[e]를 더 작은 값으로 갱신한다.

다만, 초기값이 0이므로, 특정 출발점을 기준으로 한 최단 거리라기보다는 음수 사이클을 판별하기 위한 값으로 해석해야 한다.

---

3. 실행 과정 시뮬레이션

🔹 입력 예제

1  # 테스트 케이스 개수
3 3 1  # 노드 수(n), 도로 수(m), 웜홀 수(w)
1 2 3  # 도로 (1 ↔ 2, 가중치 3)
2 3 4  # 도로 (2 ↔ 3, 가중치 4)
3 1 8  # 도로 (3 ↔ 1, 가중치 8)
3 2 2  # 웜홀 (3 → 2, 가중치 -2)

🔹 dist 배열 변화 (초기값: [0, 0, 0, 0])

반복 횟수	갱신된 dist 배열
0회	[0, 0, 0, 0]
1회	[0, 0, 3, 7]
2회	[0, 0, 3, 5]
3회	(갱신 발생) → "YES" 반환 (음수 사이클 존재)

설명:

• 1회 반복: 1 → 2 (3), 2 → 3 (7), 3 → 1 (8)을 갱신
• 2회 반복: 웜홀 3 → 2 (-2)로 인해 dist[2]가 3으로 감소
• 3회 반복: 또다시 갱신이 발생하면 음수 사이클이 존재하므로 "YES"를 반환

---

4. 핵심 요약

✅ n-1번 반복하는 이유: 최단 경로의 최대 간선 개수가 n-1개이기 때문
✅ dist[e]의 의미: "어떤 출발점에서 시작했는지는 모르지만, 현재까지의 최소 비용(시간)"
✅ 추가 반복(n번째 반복)의 역할: 음수 사이클이 존재하는지 확인하기 위해 필요

---

🎯 결론

Bellman-Ford 알고리즘을 사용하면 음수 사이클의 존재 여부를 효과적으로 판별할 수 있다. 특히, 이 문제에서는 모든 노드를 출발점으로 간주하여 dist를 0으로 초기화한 후, n-1번 반복한 뒤 한 번 더 반복하여 음수 사이클이 있는지 확인하는 방식으로 해결하였다.