벨만-포드 알고리즘 완벽 이해하기

1. 벨만-포드 알고리즘이란?

벨만-포드(Bellman-Ford)는 음수 가중치가 포함된 그래프에서 최단 경로를 찾는 알고리즘이다.

다익스트라 vs 벨만-포드

구분	다익스트라 (Dijkstra)	벨만-포드 (Bellman-Ford)
음수 가중치	불가능	가능
음수 사이클 감지	불가능	가능
시간 복잡도	O(E log V)	O(V × E)
구현 특징	우선순위 큐 사용	모든 간선을 V-1번 반복

---

2. 핵심 원리

2.1 왜 V-1번 반복할까?

최단 경로는 최대 V-1개의 간선을 포함한다.
(사이클이 없는 한, 더 이상 추가 간선을 거치지 않아도 모든 노드에 도달 가능)

반복 횟수	의미
0	시작점
1	시작점 → 1개 간선
2	시작점 → 2개 간선
...	...
V-1	시작점 → V-1개 간선 (모든 노드 도달 가능)

2.2 음수 사이클 감지

V번째 반복에서도 거리가 갱신된다면, 음수 사이클이 존재한다는 의미다.

// V-1번 완화
for (int i = 1; i < V; i++) {
    for (모든 간선 u → v) {
        if (dist[u] + weight < dist[v]) {
            dist[v] = dist[u] + weight;
        }
    }
}

// V번째 반복 - 음수 사이클 감지
for (모든 간선 u → v) {
    if (dist[u] + weight < dist[v]) {
        return "음수 사이클 존재!";
    }
}

---

3. 문제별 적용 분석

문제 1: 1865번 - 웜홀 (음수 사이클 감지)

핵심 아이디어

• 일반 도로: 양방향, 양수 가중치
• 웜홀: 단방향, 음수 가중치 (시간을 되돌림)
• 음수 사이클이 존재한다면 “출발 시간보다 더 이전으로 돌아올 수 있음”

가상 노드 추가

for (int i = 1; i <= inputArr[0]; i++) {
    graph.computeIfAbsent(0, k -> new ArrayList<>())
         .add(new int[]{i, 0});  // 0 → 모든 노드, 가중치 0
}

이유

• 시작점이 정해지지 않음
• 어느 노드에서든 음수 사이클 존재 여부를 확인해야 함
• 가상 노드 0에서 모든 노드로 가중치 0으로 연결하면 전체 탐색 가능

---

문제 2: 1738번 - 골목길 (최장 경로 + 양의 사이클)

핵심 아이디어

• 최단 경로가 아닌 최장 경로를 구하는 문제
• 가중치를 음수로 변환하여 벨만-포드로 풀이
• 양의 사이클이 존재하면 무한히 돈을 벌 수 있음 → -1 출력

양의 사이클 감지 및 전파

boolean[] inPositiveCycle = new boolean[n + 1];

// 1단계: 양의 사이클 존재 확인
for (모든 간선 u → v) {
    if (balance[u] + w > balance[v]) {
        inPositiveCycle[v] = true;
    }
}

// 2단계: 사이클 영향 전파 (V-1번 반복)
for (int i = 1; i < n; i++) {
    for (모든 간선 u → v) {
        if (inPositiveCycle[u]) {
            inPositiveCycle[v] = true;
        }
    }
}

왜 전파가 필요한가?

• 양의 사이클은 탐지했지만, 그 영향을 받는 노드들도 표시해야 한다.
• 사이클에 연결된 노드는 모두 무한 이득 가능.

---

문제 3: 1219번 - 오민식의 고민 (복합 문제)

핵심 아이디어

• 이동 경로에 따른 교통비와 도시별 수입이 모두 고려됨
• 양의 사이클로 인해 무한히 돈을 벌 수 있는지 판단
• 목적지까지 도달 가능한지 확인해야 함

복합 갱신 조건

if(balance[u] != Long.MIN_VALUE &&
   balance[u] + w + earn[v] > balance[v]) {
    balance[v] = balance[u] + w + earn[v];
}

BFS로 사이클 영향 전파

Queue<Integer> queue = new LinkedList<>();
for (int i = 0; i < N; i++) {
    if (inPositiveCycle[i]) queue.offer(i);
}

while (!queue.isEmpty()) {
    int u = queue.poll();
    if(graph.containsKey(u)) {
        for(var edge : graph.get(u)) {
            int v = edge[0];
            if (!inPositiveCycle[v]) {
                inPositiveCycle[v] = true;
                queue.offer(v);
            }
        }
    }
}

BFS 방식은 불필요한 반복 완화를 줄여 효율적이다.

---

4. 구현 패턴 정리

기본 벨만-포드 템플릿

// 1. 초기화
int[] dist = new int[N];
Arrays.fill(dist, Integer.MAX_VALUE);
dist[start] = 0;

// 2. V-1번 완화
for (int i = 1; i < N; i++) {
    for (모든 간선 u → v, weight w) {
        if (dist[u] != Integer.MAX_VALUE &&
            dist[u] + w < dist[v]) {
            dist[v] = dist[u] + w;
        }
    }
}

// 3. 음수 사이클 감지
for (모든 간선 u → v, weight w) {
    if (dist[u] != Integer.MAX_VALUE &&
        dist[u] + w < dist[v]) {
        // 음수 사이클 존재!
    }
}

변형 패턴

문제 유형	변형 방식
최장 경로	가중치 부호 반전, 비교 부등호 반대
시작점 불명	가상 노드 추가
사이클 영향 전파	BFS/DFS 또는 V-1번 추가 완화
복합 계산	갱신 시 수입/비용 포함

---

5. 주의사항

5.1 무한대 처리

// 잘못된 방식
if (dist[u] + w < dist[v])

// 올바른 방식
if (dist[u] != Integer.MAX_VALUE && dist[u] + w < dist[v])

5.2 사이클 감지만으로는 부족

• 사이클이 있어도 목적지와 관련 없으면 결과에 영향 없음
• 반드시 사이클 → 목적지 연결 여부 확인 필요

5.3 자료형 주의

• 1219번의 경우 돈 단위가 커질 수 있으므로 long 사용 필수

---

6. 시간복잡도 분석

• 기본 벨만-포드: O(V × E)
  • V-1번 반복 × 각 반복에서 E개의 간선 확인
• 사이클 전파 추가 시: BFS → O(V + E)
  • 완화 방식 전파(1738번)는 여전히 O(V × E)

총합: O(V × E)

---

7. 언제 벨만-포드를 사용할까?

사용해야 하는 경우	사용하지 말아야 하는 경우
음수 가중치 존재	모든 가중치가 양수
음수/양수 사이클 감지 필요	단순 최단 경로 탐색
시작점이 불명확	그래프가 매우 큼 (V × E 과다)

---

정리

세 문제는 모두 벨만-포드의 핵심인 V-1번 완화 + V번째 사이클 감지 원리를 기반으로 한다.
하지만 각 문제는 그래프 구조나 요구 조건에 맞게 다음과 같이 변형되었다.

문제	주요 포인트
1865 웜홀	음수 사이클 감지, 가상 노드 활용
1738 골목길	최장 경로 + 양의 사이클 전파
1219 오민식의 고민	수입/비용 계산 + BFS 전파

결국 벨만-포드는 “경로 완화 기반의 상태 갱신 알고리즘”이다.
그래프가 복잡해질수록, 이 기본 구조를 문제에 맞게 변형하는 능력이 중요하다.