[BOJ 1865] (벨만 포드) 웜홀 (C++)

웜홀 (Gold 3)

문제

전체 문제 보기

1865번: 웜홀

접근법

이번 문제는 음의 가중치가 주어지는 그래프에서 음의 사이클 여부를 파악하는 문제입니다. 간선에 가중치가 없는 그래프에서 최단 경로를 찾기 위해서는 BFS가 가장 효율적입니다. 만약 가중치가 존재한다면 다익스트라 알고리즘을 활용할 수 있습니다. 하지만 다익스트라 알고리즘은 반드시 모든 가중치는 양수가 보장되어야 한다는 단점이 있습니다. 음의 가중치를 가진 간선이 존재한다면 벨만 포드 알고리즘을 통해서 구할 수 있습니다. 벨만 포드는 출발 노드와 연결된 모든 간선의 비용을 최저값으로 갱신하며 진행됩니다. 그래서 가장 비용이 적은 노드만 골라서 최저값을 갱신하는 다익스트라 알고리즘의 시간 복잡도가 $O(E + N\mbox{log}N)$인 반면 벨만 포드의 시간 복잡도는 $O(E\cdot N)$으로 조금 더 높습니다. 이번 문제에서는 웜홀이라는 음의 가중치를 가진 간선이 존재합니다. 그래서 BFS, 다익스트라 알고리즘을 사용할 수 없고 벨만 포드 알고리즘을 사용해야 합니다.

벨만 포드 알고리즘은 모든 간선의 가중치를 N번 갱신하면 모든 노드로 이동하는 최소값을 구할 수 있다는 특징이 있습니다. 아래의 코드처럼 말이죠.

distances[1] = 0;    // 출발 노드의 이동 비용을 0으로 설정 한다. // 그외 모든 노드의 이동 비용은 INF
    for (int i = 0; i < N; ++i) // 노드의 갯수만큼 반복한다.
    {
        for (auto edge : edges) // 모든 간선에 이동 비용을 최소 비용으로 갱신한다.
        {    
            if (distances[edge.end] > distances[edge.start] + edge.time)
            {
                distances[edge.end] = distances[edge.start] + edge.time;
            }
        }
    }

음의 사이클

문제의 웜홀을 이야기 하기 전에 먼저 음의 사이클에 대해서 이야기할 필요가 있습니다. 벨만 포드 알고리즘은 음의 사이클이 존재할 경우 최단 거리를 구할 수 없습니다. 음의 사이클이란 다음과 같습니다.

출발지점 s 노드 에서 e로 가기 위한 최단거리를 구하고자 합니다. 만약 b를 거치지 않고 s->a->c 까지 이동한다면 비용이 8이 필요합니다. 하지만 b를 지나서 s->a->b->c로 이동하게 되면 비용이 -4가 됩니다. 그런데 여기서 멈추지 않고 다시 a->b->c로 한 번 더 회전을 한다면 비용을 더 줄일 수 있습니다. s->a->b->c->a->b->c 이렇게 이동할 경우 비용은 -6이 됩니다. 사이클을 한번 더 돌아서 s->a->b->c->a->b->c->a->b->c 가 될 경우 비용은 -8이 됩니다. 즉, 사이클은 무한히 돌 수 있으며 돌 때마다 비용은 계속 작아지게 됩니다. 그래서 음의 사이클이 존재할 경우 최소 비용을 구할 수 없게 됩니다.

 

그런데 벨만 포드 알고리즘은 음의 사이클을 탐지하기 위해서도 사용될 수 있습니다. 왜냐하면 벨만 포드 알고리즘은 음의 사이클이 존재하지 않을 경우 노드의 개수만큼 모든 간선을 갱신하면 반드시 모든 갱신이 끝나게 됩니다. 그런데, 노드의 개수 만큼 갱신을 했음에도 노드 개수 + 1 번째 반복문에서도 갱신이 발생했다면 음의 사이클이 존재한다고 볼 수 있습니다. 그래서 아래의 코드처럼 N+1회 반복을 하며, 음의 사이클을 탐지할 수 있습니다.

    for (int i = 0; i < N + 1; ++i)
    {
        for (auto edge : edges)
        {
            if (distances[edge.end] > distances[edge.start] + edge.time)
            {
                distances[edge.end] = distances[edge.start] + edge.time;

                // 음의 순환이 존재하는 경우
                if (i == N)
                    return true;
            }
        }
    }

음의 사이클 탐지

그럼 다시 웜홀 이야기로 돌아가서 이야기를 계속하겠습니다. 문제에서 "한 지점에서 출발을 하여서 시간여행을 하기 시작하여 다시 출발을 하였던 위치로 돌아왔을 때, 출발을 하였을 때보다 시간이 되돌아가 있는 경우" 가 있는지를 물었습니다. 양의 가중치를 가진 사이클만 존재할 경우 절대 불가능한 일입니다. 그리고 하나의 사이클의 비용이 0 이 되면 사이클을 돌며 시간을 유지할 수는 있지만, 되돌릴 수는 없습니다. 결국 사이클이 존재하는 그래프에서, 음의 사이클이 존재할 경우만 시간을 되돌릴 수 있습니다. 그래서 이 문제는 주어진 그래프에서 음의 사이클이 존재하는지 묻는 문제입니다. 그래서 앞서 언급한 음의 사이클을 탐지하는 알고리즘으로 문제를 풀 수 있습니다.

전체 코드

#include <iostream>
#include <array>
#include <vector>
#include <queue>
#define endl '\n'
using namespace std;

const int INF = 2'000'000'000;

struct Edge {
    Edge(int _start, int _end, int _time) : start(_start), end(_end), time(_time) {}
    int start;
    int end;
    int time;
};

bool Solve()
{
    vector<Edge> edges;
    vector<int> distances;

    int N; // 지점의 수 N(1 ≤ N ≤ 500)
    int M; // 도로의 개수 M(1 ≤ M ≤ 2500)
    int W; // 웜홀의 개수 W(1 ≤ W ≤ 200)

    cin >> N >> M >> W;

    edges.reserve(M);
    distances.resize(N+1, INF);

    for (int i = 0; i < M; ++i)
    {
        int S, E, T;
        cin >> S >> E >> T;
        edges.emplace_back(S, E, T);
        edges.emplace_back(E, S, T);
    }

    for (int i = 0; i < W; ++i)
    {
        int S, E, T;
        cin >> S >> E >> T;
        edges.emplace_back(E, S, -T);
    }

    // 벨만-포드
    // 시작점
    distances[1] = 0;
    for (int i = 0; i < N + 1; ++i)
    {
        for (auto edge : edges)
        {
            if (distances[edge.end] > distances[edge.start] + edge.time)
            {
                distances[edge.end] = distances[edge.start] + edge.time;

                // 음의 순환이 존재하는 경우
                if (i == N)
                    return true;
            }
        }
    }

    return false;
}
int main() {
    //입출력 성능향상을 위한 설정
    ios_base::sync_with_stdio(false);
    cout.tie(NULL);
    cin.tie(NULL);

    int TC;
    cin >> TC;
    while (TC--)
    {
        if (Solve())
            cout << "YES" << endl;
        else
            cout << "NO" << endl;
    }

    return 0;
}

성능 평가

간선의 수를$E$ 노드의 수를 $N$ 이라고 했을 때 시간 복잡도는 앞서 언급한 대로 $O(E\cdot N)$ 입니다. 공간 복잡도는 간선 개수만큼 간선 배열과, 노드 개수만큼의 거리 배열을 사용했기 때문에 $O(E + N)$ 입니다.