[회고록]1e9 와 오버플로우

프로그래머스 문제 - 합승 택시 요금

합승 택시 요금 ,, 오늘도 당하고 말았다. 컴퓨터 구조에 대한 지식을 얕잡아 보면 안되었다. 이번 문제는 그래프 문제로 시작 지점 s와 다른 두 지점 a와 b가 있을때 a와 b로 갈 수 있는 최저 비용을 구하는 간단한(?) 문제이다. 나는 대표적인 그래프 알고리즘으롤 세가지를 떠올렸다.

플로이드, 다익스트라 그리고 크루스칼이다. 아무래도 효율성 점수가 있는 문제이기에 다익스트라나 크루스칼로 푸는 것이 시간복잡도 면에서 낫지 않을까 생각했다. 하지만 이 문제에서 정점의 갯수 n은 최대 200 까지 였기에 O(N^3) 시간 복잡도를 가지는 플로이드 알고리즘으로 해결해도 최대 8,000,000 의 복잡도를 가져서 효율성문제를 통과할것 같았다.

그래서 코드를 다 작성하고 제출을 했으나 결과는..

대체 어디서 잘못된걸까?

우선 오답 결과를 받은 코드를 먼저 살펴 보겠다.

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
#define INF 1e9
int dp[201][201];

int solution(int n, int s, int a, int b, vector<vector<int> > fares) {
    int answer = INF;

    for(int i = 1; i <= n; i++){
        fill_n(dp[i], n + 1, INF); // 어느 지점과도 연결되어있지 않다는 의미로 무제한 값으로 초기화
        dp[i][i] = 0;
    }

    // 플로이드를 위해 충분히 큰 값으로 초기화
    for(int i = 0; i < fares.size(); i++){ // 양방향 비용으로 초기화
        dp[fares[i][0]][fares[i][1]] = fares[i][2];
        dp[fares[i][1]][fares[i][0]] = fares[i][2];
    }
    // 플로이드 와샬알고리즘으로 모든 각 간선 다른 모든 간선으로 가는 최소비용을 구함
    for(int through = 1; through <= n; through++){
        for(int from = 1; from <= n; from++){
            for(int to = 1; to <= n; to++){
                dp[from][to] = min(dp[from][to], dp[from][through] + dp[through][to]);
            }
        }
    }
    
    // 그리고 (출발지점(s)->다른지점(i)) + (다른지점(i)->A지점) +  (다른 지점(i)->B지점)
    // 중에서 가장 최소값을 구함
    for(int i = 1; i <= n; i++){
        answer = min(answer, dp[s][i] + dp[i][a] + dp[i][b]);
    }
    return answer;
}

아무리 봐도 틀린 것이 없어 보이는 이 코드는 단 한줄에 의해 오답과 정답으로 갈린다.

#define INF 1e9

왜 이것 떄문이냐? 생각을 차근차근 해보도록 하자. 우선은 1e9 == 1,000,000,000 을 의미한다. 즉 정수형으로 10억이다. 그 다음으로 정수형의 범위를 한번 알아보자. -2,147,483,647 ~ 2,147,483,647 이다. 이렇기 때문에 1,000,000,000 을 최대 두번 더할 수 있고, 그 이상을 더하면 오버플로우가 발생한다. 정리를 한번 해보자.

1e9 : 1,000,000,000 (10억)
정수 범위 : -2,147,483,647 ~ 2,147,483,647

이렇기에 1e9를 세번 더하면 오버플로우가 발생하여 처음 값으로 돌아가 음수가 되어 버린다!!!! 즉 -1,294,967,296 가 되어 버린다.
그럴일이 있느냐? 있다!

    // 그리고 (출발지점(s)->다른지점(i)) + (다른지점(i)->A지점) +  (다른 지점(i)->B지점)
    // 중에서 가장 최소값을 구함
    for(int i = 1; i <= n; i++){
        answer = min(answer, dp[s][i] + dp[i][a] + dp[i][b]);
    }

위 코드에서 dp[s][i], dp[i][a] 그리고 dp[i][b] 가 모두 10억을 가지는 경우이다. 이렇게 되면 제대로된 최소 비용을 구할수 없다. 연결된 간선이 없다는 의미로 10억을 준건데 그럼 어떻게 해야할까? 답은 간단하다. INF의 값을 10억의 값이 아닌 적당하게 큰 값, 예를 들어 5,000,000 로 정의하거나, abs() 함수를 이용해 음수가 나올수 없도록 해주면 된다. 아래 코드처럼..

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
#define INF 1e9
int dp[201][201];

//problem link: https://programmers.co.kr/learn/courses/30/lessons/72413

int solution(int n, int s, int a, int b, vector<vector<int> > fares) {
    int answer = INF;

    for(int i = 1; i <= n; i++){
        fill_n(dp[i], n + 1, INF); // 어느 지점과도 연결되어있지 않다는 의미로 무제한 값으로 초기화
        dp[i][i] = 0;
    }

    // 플로이드를 위해 충분히 큰 값으로 초기화
    for(int i = 0; i < fares.size(); i++){ // 양방향 비용으로 초기화
        dp[fares[i][0]][fares[i][1]] = fares[i][2];
        dp[fares[i][1]][fares[i][0]] = fares[i][2];
    }

    // 플로이드 와샬알고리즘으로 모든 각 간선에서 다른 모든 간선으로 가는 최소비용을 구함
    for(int through = 1; through <= n; through++){
        for(int from = 1; from <= n; from++){
            for(int to = 1; to <= n; to++){
                // abs 함수 사용 이유 : 오버플로 발생시 음수 값으로 변할 경우때문에
                dp[from][to] = min(dp[from][to], abs(dp[from][through] + dp[through][to]));
            }
        }
    }
    
    // 그리고 (출발지점(s)->다른지점(i)) + (다른지점(i)->A지점) +  (다른 지점(i)->B지점)
    // 중에서 가장 최소값을 구함
    for(int i = 1; i <= n; i++){
        answer = min(answer, abs(dp[s][i] + dp[i][a] + dp[i][b])); // abs 함수 사용 이유 : 오버플로 발생시 음수 값으로 변할 경우때문에
    }

    return answer;
}