[99클럽/코딩테스트 챌린지/C++] 음수 사이클 감지 문제와 해결 과정 (벨만-포드 알고리즘)

문제 링크 : 

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

 

---

풀이 과정

알고리즘 선택: 벨만-포드 알고리즘

• 벨만-포드 알고리즘은 다음 특징을 가진다:
  1. 음수 가중치를 포함한 그래프에서도 최단 경로를 계산할 수 있다.
  2. 음수 사이클이 존재하는 경우 이를 탐지할 수 있다.
• 핵심 아이디어:
  • N−1N-1N−1번 간선 완화를 수행하여 최단 거리를 계산한다.
  • NNN-번째 간선 완화를 추가로 실행하여, 값이 갱신되면 음수 사이클이 존재한다고 판단한다.

---

문제 상황

음수 사이클이 정상적으로 동작하지 않아 " 출력 초과 " 메세지가 나옴

---

 

문제 원인

음수 누적에 따른 정수 오버플로우 발생

• 가중치의 범위가 −10,000≤C≤10,000-10,000 \leq C \leq 10,000−10,000≤C≤10,000으로 충분히 크며, 음수 값이 반복적으로 누적되면서 int 타입의 범위를 초과함.
• C++에서 int는 32비트 정수형으로, 표현 가능한 값의 범위는: −2,147,483,648≤x≤2,147,483,647-2,147,483,648 \leq x \leq 2,147,483,647−2,147,483,648≤x≤2,147,483,647
• 그러나 C×M=−10,000×6,000=−60,000,000C \times M = -10,000 \times 6,000 = -60,000,000C×M=−10,000×6,000=−60,000,000과 같이 음수 누적 시 범위를 초과.

---

해결 방법

1, dist 배열을 long long으로 변경

• −60,000,000-60,000,000−60,000,000과 같은 음수 누적 값을 안전하게 처리하기 위해 dist 배열을 long long 타입으로 선언.

---

최종 코드

// ConsoleApplication4.cpp : 이 파일에는 'main' 함수가 포함됩니다. 거기서 프로그램 실행이 시작되고 종료됩니다.
//

#include <algorithm>
#include <iostream>
#include <tuple>
#include <vector>

#define MAX 99999999
using namespace std;

int N, M;
vector<tuple<int, int, int>> busTimes;
vector<long long> dist;

int main()
{
    ios::sync_with_stdio(false); // 입출력 속도 최적화
    cin.tie(nullptr);

    std::cin >> N >> M;
    dist = vector<long long>(N + 1, MAX);
    dist[1] = 0;

    for (int i = 0; i < M; i++)
    {
        int a, b, c = 0;
        std::cin >> a >> b >> c;
        busTimes.push_back(make_tuple(a, b, c));
    }

    for (int i = 1; i < N; i++) {
        for (auto val : busTimes)
        {
            int start = get<0>(val);
            int end = get<1>(val);
            int time = get<2>(val);
            if (dist[start] == MAX) continue;
            dist[end] = std::min(dist[start] + time, dist[end]);
        }
    }

    for (auto val : busTimes)
    {
        int start = get<0>(val);
        int end = get<1>(val);
        int time = get<2>(val);
        if (dist[start] == MAX) continue;
        if (dist[start] + time < dist[end])
        {
            cout << -1 << '\n';
            return 0;
        }
    }

    // 결과 출력
    for (int i = 2; i <= N; i++) {
        if (dist[i] == MAX)
            cout << -1 << '\n'; // 경로가 없는 경우
        else
            cout << dist[i] << '\n'; // 최단 거리 출력
    }
}

---

결론

• 오버플로우 문제를 해결하기 위해 long long 타입을 도입한 것이 핵심.
• 입력 데이터의 범위와 가중치의 누적 효과를 항상 고려해야 한다는 것을 깨달음.
• 벨만-포드 알고리즘은 음수 사이클 문제를 탐지하고, 큰 범위의 그래프 문제를 처리하는 데 유용하다는 점을 다시 확인.

---

배운 점

1, 자료형 선택의 중요성:

• 문제 조건과 입력 범위를 항상 주의 깊게 분석.
• 큰 값을 처리할 가능성이 있다면 long long과 같은 넉넉한 자료형을 고려.

2, 디버깅 과정:

• 음수 사이클 문제에서 범위 초과를 의심하여 dist 값을 확인하고, 오버플로우 문제를 발견.

3, 알고리즘 이해:

• 벨만-포드 알고리즘의 음수 사이클 탐지 메커니즘을 명확히 이해.