[백준/BOJ] 11657번: 타임머신 ( 벨만-포트 알고리즘 ) - C++ 문제 풀이

문제 설명

 

문제 링크: https://www.acmicpc.net/problem/11657

 

풀이

이 문제는 1번 도시에서 출발하여, 다른 도시까지 이동하는 데 걸리는 가장 빠른 시간을 출력하는 문제입니다.

 

이러한 문제를 푸는데 적용할 알고리즘으로 다익스트라( Dijkstra )와 벨만-포드( Bellman-Ford ) 알고리즘이 있습니다.

그런데, 주의할 점은, 이동하는 데 걸리는 시간이 음수인 경우가 있다는 것입니다.

 

다익스트라 알고리즘의 경우 음수 입력 데이터에 따라 문제를 해결하지 못할 수도 있습니다.

따라서, 벨만-포드 알고리즘을 사용합니다.

 

벨만-포드 알고리즘에 관한 내용은 여기에서 볼 수 있습니다.

[C++] 최단 거리를 구하는 벨만-포드( Bellman-Ford ) 알고리즘

 

이 알고리즘을 사용하기 위해서 먼저 그래프를 구성합니다.

using mtype = long;
using edge = tuple<int, int, int>;  // 시작 정점, 종료 정점, 가중치

#define SIZE    500     // 정점의 개수
mtype minDist[SIZE+1];  // 정점까지의 최단 거리를 저장

vector<edge> Edges;     // 간선 벡터

//-------------------------------------------------------------

int N, M;
cin >> N >> M;	// N: 정점 개수, M: 간선 개수

int A, B, C;
for( int i = 0; i < M; i++){
    cin >> A >> B >> C;

    Edges.emplace_back( A, B, C);
}

// 벨만-포드 알고리즘 호출
bool bExistCycle = bellman_ford(N);	// N: 정점 개수

이때, 각 간선은 < 시작 정점, 종료 정점, 가중치( 이동에 걸리는 시간 ) >으로 이루어져 있습니다.

 

벨만-포드( Bellman-Ford ) 알고리즘을 코드로 작성한 것은 다음과 같습니다.

int bellman_ford(int V){    // V: 정점 개수

    int M = Edges.size();   // 간선 개수
    
    for( int i = 1; i <= V; i++){
        minDist[i] = LONG_MAX;   // 초기화
    }

    minDist[1] = 0;

    for( int i = 0; i < V-1; i++){
        for( int j = 0; j < M; j++){
            
            const edge& eg = Edges[j];
            int s = get<0>(eg);
            int e = get<1>(eg);
            int w = get<2>(eg);
            
            if ( minDist[s] != LONG_MAX){
                if ( minDist[e] > minDist[s] + w)
                    minDist[e] = minDist[s] + w;
            }
        }
    }

    bool bExistCycle = false;	// 음수 가중치 순환 경로가 있는지 확인

    for( int j = 0; j < M; j++){
            
        const edge& eg = Edges[j];
        int s = get<0>(eg);
        int e = get<1>(eg);
        int w = get<2>(eg);
        
        if ( minDist[s] != LONG_MAX){
            if ( minDist[e] > minDist[s] + w){
                bExistCycle = true;
                break;
            }
        }
    }

    return bExistCycle;
}

이 함수가 종료되면, minDist 배열에 출발 정점으로부터 다른 정점까지의 최단 시간이 저장됩니다.

이제, 이 결과를 출력하면 문제 해결.

bool bExistCycle = bellman_ford(N);	// N: 정점 개수

if ( bExistCycle){
    // 음수 가중치 순환 경로가 있으면 최단거리를 구할 수 없습니다. 
    cout << -1 << endl;	
}
else{

    for( int i = 2; i <= N; i++){
        if ( minDist[i] == LONG_MAX){	// 도달할 수 없는 도시
            cout << -1 << endl;
        }
        else{
            cout << minDist[i] << endl;
        }
    }
}

 

참고로, 결과를 담을 배열을 int 타입으로 하면, "출력 초과" 오류를 만나게 됩니다.

 

소스 코드

#include <iostream>
#include <vector>
#include <tuple>
#include <limits.h>
using namespace std;

using mtype = long;
using edge = tuple<int, int, int>;  // 시작 정점, 종료 정점, 가중치

#define SIZE    500     // 정점의 개수
mtype minDist[SIZE+1];  // 정점까지의 최단 거리를 저장

vector<edge> Edges;     // 간선 벡터

int bellman_ford(int V){    // V: 정점 개수

    int M = Edges.size();   // 간선 개수
    
    for( int i = 1; i <= V; i++){
        minDist[i] = LONG_MAX;   // 초기화
    }

    minDist[1] = 0;

    for( int i = 0; i < V-1; i++){
        for( int j = 0; j < M; j++){
            
            const edge& eg = Edges[j];
            int s = get<0>(eg);
            int e = get<1>(eg);
            int w = get<2>(eg);
            
            if ( minDist[s] != LONG_MAX){
                if ( minDist[e] > minDist[s] + w)
                    minDist[e] = minDist[s] + w;
            }
        }
    }

    bool bExistCycle = false;

    for( int j = 0; j < M; j++){
            
        const edge& eg = Edges[j];
        int s = get<0>(eg);
        int e = get<1>(eg);
        int w = get<2>(eg);
        
        if ( minDist[s] != LONG_MAX){
            if ( minDist[e] > minDist[s] + w){
                bExistCycle = true;
                break;
            }
        }
    }

    return bExistCycle;
}

int main(){

    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    int N, M;
    cin >> N >> M;

    int A, B, C;
    for( int i = 0; i < M; i++){
        cin >> A >> B >> C;

        Edges.emplace_back( A, B, C);
    }

    bool bExistCycle = bellman_ford(N);

    if ( bExistCycle){
        cout << -1 << endl;
    }
    else{

        for( int i = 2; i <= N; i++){
            if ( minDist[i] == LONG_MAX){
                cout << -1 << endl;
            }
            else{
                cout << minDist[i] << endl;
            }
        }
    }
        
    return 0;
}