[C++] BOJ 11657번 : 타임머신

 

 

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

 

문제 3줄 요약

1. N개의 도시가 있다. 1번 도시가 기준이다.

2. 도시를 건너는 버스는 시작 도시, 도착 도시, 걸리는 시간(양수가 아닌 경우 존재)으로 표현한다.

3. 나머지 도시로 가는 가장 빠른 시간을 구해라.

 

---

 

 

만약 시간을 무한히 오래 전으로 되돌릴 수 있다면 -1을 출력한다.

 

2번 도시부터 차례대로 시간을 출력하되

해당 도시로 가는 경로가 없는 경우 또한 -1을 출력한다.

 

---

 

여기서

무한히 오래 전으로 되돌릴 수 있다는게 무슨 뜻 일까?

 

걸리는 시간 C가 음수이며,

음수가 포함된 경로가 순환을 이루면

반복을 통해 최단 시간이 무한한 음수로 가는 경우를 뜻하게 된다.

 

따라서

최단 경로 알고리즘인 다익스트라 알고리즘은 사용할 수 없으며,

벨만-포드 알고리즘을 사용해야 한다.

 

벨만포드 알고리즘을

아래 영상을 참고하였다!

 

https://www.youtube.com/watch?v=0NrlN88D9Fs

 

 

---

 

먼저 입력 값과 필요한 저장 공간을 할당한다.

 

#include <iostream>
#include <vector>

using namespace std;

struct info {
    int x, y;
    long long z;
};

int inf = 1e9;
long long node[501];

vector<info> value;

int main(void){
    ios::sync_with_stdio(0); // c stream, c++ stream 중 c++ stream만 사용
    cin.tie(0); // 버퍼 비우지 않음

    int n, m;
    cin >> n >> m;

    fill(node+2, node+n+1, inf);

    for(int i=0; i<m; i++)
    {
        int a, b;
        long long c;
        cin >> a >> b >> c;
        value.push_back({a, b, c});
    }

    return 0;
}

 

1번 도시부터 시작하기 때문에

2번 도시부터 ~ n번 도시까지의 최단 거리 값을

inf 값으로 설정해준다.

 

구조체를 사용하여

{ 시작 도시, 도착 도시, 걸리는 시간 } 을

vector에 저장한다.

 

---

 

이후

벨만 포드 알고리즘을 이용하여

최단 거리를 탐색한다.

 

bool search(int n, int m){

    for(int i=0; i<n; i++)
    {
        for(info v : value)
        {
            int cur = v.x, next = v.y;
            long long cost = v.z;
            
            if(node[cur] != inf && (node[next] > node[cur] + cost)){
                node[next] = node[cur]+cost;
                if (i == n-1) return true;
            }
        }
    }

    return false;
}

 

(정점 개수 - 1)만큼 Round를 반복해주며

모든 간선을 살펴본다.

 

이때 방문했던 노드 중에서

Relax가 가능한 도시가 발견된다면 Relax 해준다.

 

여기서 Relax는

(기존의 최단 거리 > 시작 도시의 최단거리 + 걸린 시간) 일 경우

해당 값으로 바꿔주는 것을 의미한다.

 

여기서

Relax 한 Round가 정해진 Round 수를 지난 n-1이라면 음수 사이클이 존재함을 의미한다.

이때 true를 반환하여 첫 번째 예외 처리를 수행한다.

 

---

 

    bool result = search(n, m);

    if (result) cout << "-1";
    else{
        for(int i=2; i<=n; i++){
            if(node[i] == inf) cout << "-1\n";
            else cout << node[i] << "\n";
        }
    }

 

search의 값이 false라면

이제 2번 도시부터 차례대로 최단 거리를 출력해준다.

이때 도시를 방문하지 않아

최단 거리가 inf와 같다면 "-1"을 출력해준다.

 

 

따라서 정답 코드는 아래와 같다.

 

#include <iostream>
#include <vector>

using namespace std;

struct info {
    int x, y;
    long long z;
};

int inf = 1e9;
long long node[501];

vector<info> value;

bool search(int n, int m){

    for(int i=0; i<n; i++)
    {
        for(info v : value)
        {
            int cur = v.x, next = v.y;
            long long cost = v.z;
            
            if(node[cur] != inf && (node[next] > node[cur] + cost)){
                node[next] = node[cur]+cost;
                if (i == n-1) return true;
            }
        }
    }

    return false;
}

int main(void){
    ios::sync_with_stdio(0); // c stream, c++ stream 중 c++ stream만 사용
    cin.tie(0); // 버퍼 비우지 않음

    int n, m;
    cin >> n >> m;

    fill(node+2, node+n+1, inf);

    for(int i=0; i<m; i++)
    {
        int a, b;
        long long c;
        cin >> a >> b >> c;
        value.push_back({a, b, c});
    }

    bool result = search(n, m);

    if (result) cout << "-1";
    else{
        for(int i=2; i<=n; i++){
            if(node[i] == inf) cout << "-1\n";
            else cout << node[i] << "\n";
        }
    }

    return 0;
}

 

---

 

다익스트라 알고리즘 문제는 풀어봤지만

벨만-포드 알고리즘은 처음 풀어보았다.

 

생각보다 알고리즘 자체는 쉬웠지만

디테일한 조건들은 좀 주의해야할 필요가 있다 느꼈다.

 

끝!