[백준] 11657번 : 타임머신

문제

 

---

풀이

 

보통의 최단거리는 다익스트라 알고리즘을 사용하지만

간선의 가중치가 음수인 경우 다익스트라를 무한루프에 빠질 수 있다.

어떤 경우에 그렇게 되는지는 내가 설명하긴 귀찮고 구글에 자료가 많으니 검색해보면 될 것이다.

 

아무튼 그럴때 쓰는 방법이 벨만-포드 알고리즘인데

정점을 기준으로 최단거리를 갱신해 나가는 다익스트라와 달리 이건 간선을 기준으로 최단거리를 갱신한다.

 

정점 A, B, C가 있다고 하자. 정점의 개수 V는 3이다.

아무리 멀리 돌아가도 최단경로라면 (V-1)개의 간선을 지날 것이다.

A-B-C인 경우 A-C로 가는 경로에 간선이 2개 있는 것처럼 말이다.

 

만약 V개의 간선을 지나서 갈 수 있는 최단경로라면? 이건 음의 사이클이 발생한 것이다.

그러므로 일단 V-1번동안 간선을 살펴보며 최단경로를 갱신하고, 마지막 V번째에서 최단 경로가 갱신되는지 확인하면 된다.

 

그냥 정점이 아니라 간선을 기준으로 한다는 것만 알아두고 나보다 더 잘 설명한 다른 블로그를 찾는게 좋을 것이다.

---

소스코드

 

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

using namespace std;
const int INF = 1e9;

vector<tuple<int, int, int>> edges; //간선 정보
vector<long long> min_dist; //min_dist가 갱신되던 중 underflow가 발생할 수 있으므로 long long

bool bellmanFord(int start) {
    int v = min_dist.size() - 1;

    min_dist[start] = 0;
    for (int i = 0; i < v; i++) {
        bool isChanged = false;
        for (int j = 0; j < edges.size(); j++) {
            int source = get<0>(edges[j]);
            int dest = get<1>(edges[j]);
            int weight = get<2>(edges[j]);

            if (min_dist[source] == INF) //닿을 수 없는 정점
                continue;
            long long new_dist = min_dist[source] + weight; //source를 거쳐 dest로 가는 경로
            if (new_dist < min_dist[dest]) {
                if (i == (v - 1)) //거리 갱신이 v번 째에 이루어졌다면 사이클 발생한 것
                    return true;
                min_dist[dest] = new_dist;
                isChanged = true; //거리 갱신 표시
            }
        }
        if (!isChanged) //갱신 없었다면 더 이상 탐색할 필요 없음
            return false;
    }
    return false;
}

int main() {
    int N, M, A, B, C;

    cin >> N >> M;
    min_dist.assign(N + 1, INF);
    for (int i = 0; i < M; i++) {
        cin >> A >> B >> C;
        edges.push_back(make_tuple(A, B, C));
    }
    if (bellmanFord(1)) //사이클이 발생함
        cout << -1;
    else { //사이클이 발생하지 않음
        for (int i = 2; i <= N; i++)
            cout << ((min_dist[i] == INF) ? -1 : min_dist[i]) << '\n';
    }
}

전체 소스코드다.

 

vector<tuple<int, int, int>> edges; //간선 정보
vector<long long> min_dist; //min_dist가 갱신되던 중 underflow가 발생할 수 있으므로 long long

간선 정보를 edges에 저장한다. 그리고 최단 경로를 저장하는 min_dist 벡터인데,

입력값에 따라 min_dist가 int 범위를 넘어서 갱신될 수 있다. 그래서 long long으로 선언했다.

 

    cin >> N >> M;
    min_dist.assign(N + 1, INF);
    for (int i = 0; i < M; i++) {
        cin >> A >> B >> C;
        edges.push_back(make_tuple(A, B, C));
    }

간선의 정보를 저장한다. 일방향 그래프이니 한쪽만 해주면 된다.

그리고 시작점 1에 대해 벨만-포드 알고리즘을 수행한다.

 

bool bellmanFord(int start) {
    int v = min_dist.size() - 1;

    min_dist[start] = 0;
    for (int i = 0; i < v; i++) {
        bool isChanged = false;
        for (int j = 0; j < edges.size(); j++) {
            int source = get<0>(edges[j]);
            int dest = get<1>(edges[j]);
            int weight = get<2>(edges[j]);

            if (min_dist[source] == INF) //닿을 수 없는 정점
                continue;
            long long new_dist = min_dist[source] + weight; //source를 거쳐 dest로 가는 경로
            if (new_dist < min_dist[dest]) {
                if (i == (v - 1)) //거리 갱신이 v번 째에 이루어졌다면 사이클 발생한 것
                    return true;
                min_dist[dest] = new_dist;
                isChanged = true; //거리 갱신 표시
            }
        }
        if (!isChanged) //갱신 없었다면 더 이상 탐색할 필요 없음
            return false;
    }
    return false;
}

이게 벨만-포드 알고리즘이다.

 

    int v = min_dist.size() - 1;

    min_dist[start] = 0;

간선의 개수를 변수 v에 저장하고, 시작점의 최단 거리를 초기화 한다.

 

    for (int i = 0; i < v; i++) {
        bool isChanged = false;
        for (int j = 0; j < edges.size(); j++) {
            int source = get<0>(edges[j]);
            int dest = get<1>(edges[j]);
            int weight = get<2>(edges[j]);

            if (min_dist[source] == INF) //닿을 수 없는 정점
                continue;
            long long new_dist = min_dist[source] + weight; //source를 거쳐 dest로 가는 경로
            if (new_dist < min_dist[dest]) {
                if (i == (v - 1)) //거리 갱신이 v번 째에 이루어졌다면 사이클 발생한 것
                    return true;
                min_dist[dest] = new_dist;
                isChanged = true; //거리 갱신 표시
            }
        }
        if (!isChanged) //갱신 없었다면 더 이상 탐색할 필요 없음
            return false;
    }

그리고 for문을 v번 돈다.

 

        bool isChanged = false;

이건 최단 거리의 갱신이 있었는지 체크하는 변수다.

사이클이 발생하지 않는다면 일정 횟수의 반복 이후 더이상 갱신이 일어나지 않을 것인데, 그럴 경우 불필요한 반복을 하는 것을 막고자 이런 변수를 둔 것이다.

 

        for (int j = 0; j < edges.size(); j++) {
            int source = get<0>(edges[j]);
            int dest = get<1>(edges[j]);
            int weight = get<2>(edges[j]);

            if (min_dist[source] == INF) //닿을 수 없는 정점
                continue;
            long long new_dist = min_dist[source] + weight; //source를 거쳐 dest로 가는 경로
            if (new_dist < min_dist[dest]) {
                if (i == (v - 1)) //거리 갱신이 v번 째에 이루어졌다면 사이클 발생한 것
                    return true;
                min_dist[dest] = new_dist;
                isChanged = true; //거리 갱신 표시
            }
        }

모든 간선을 하나하나 살펴본다.

만약 min_dist[source]가 INF이라면, source 정점에 도달할 수 없다는 것이다.

도달할 수 없는 정점의 간선은 살펴볼 이유가 없다.

 

도달할 수 있는 정점이라면 new_dist를 갱신하고 기존의 min_dist[dest]와 비교하는데

min_dist[dest]를 갱신할 수 있다면 갱신하고, isChanged를 true로 바꿔서 거리의 갱신이 있었음을 표시한다.

 

근데 만약 이게 v번째에 있던 일이라면 음의 사이클이 발생한 것이기 때문에 바로 true를 리턴하고 함수를 종료한다.

 

        if (!isChanged) //갱신 없었다면 더 이상 탐색할 필요 없음
            return false;

모든 간선을 돌고도 갱신이 없었다면 더이상 최단 경로가 갱신되지 않을테니 false를 리턴하고 함수를 종료한다.

 

    if (bellmanFord(1)) //사이클이 발생함
        cout << -1;
    else { //사이클이 발생하지 않음
        for (int i = 2; i <= N; i++)
            cout << ((min_dist[i] == INF) ? -1 : min_dist[i]) << '\n';
    }

메인 함수다. 벨만-포드 함수가 true를 반환했다면 -1을 출력하고 아니라면 거리를 출력한다.