[BOJ] 1865번: 웜홀 (C++)

0. 문제

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

 

도로를 양방향 양수 가중치 간선으로, 웜홀을 단방향 음수 가중치 간선으로 치환하면, 그래프에서 음수 사이클이 존재 여부를 확인하는 문제이다.

 

1. 아이디어

최단 거리 알고리즘 중 음수 사이클 존재 여부를 판단하기 쉬운 알고리즘으로 Floyd-Warshall이 먼저 떠올랐다. All-Pair Shortest Path 알고리즘이기 때문에 시간복잡도 면에서 그렇게 효율적이진 않을 수 있으나, 정점의 최대 개수 V가 500개이기 때문에 O(V^3) 알고리즘인 Floyd-Warshall도 시간 안에 동작하고, 구현이 쉽다는 장점이 있다.

 

2. 풀이

bool check_neg_cycle(std::vector<std::vector<int>> &adjmat, int n)
{
    std::vector<std::vector<int>> a(adjmat);

    for (int k = 1; k <= n; ++k)
    {
        for (int i = 1; i <= n; ++i)
        {
            for (int j = 1; j <= n; ++j)
            {
                if (a[i][j] > a[i][k] + a[k][j])
                {
                    a[i][j] = a[i][k] + a[k][j];
                }
            }
        }
    }
    for (int i = 1; i <= n; ++i)
    {
        if (a[i][i] < 0)
        {
            return true;
        }
    }
    return false;
}

Floyd-Warshall 알고리즘 수행 후, 특정 정점에서부터 해당 정점으로 돌아오는 거리가 음수일 경우 음수 사이클이 존재한다. 즉 문제에서 요구하는 시간이 줄어들고 출발 지점으로 돌아오는 방법이 존재하는 것이다.

아래는 전체 솔루션 코드이다.

#include <iostream>
#include <vector>

#define INF 1 << 29

struct edge
{
    int u;
    int v;
    int w;
};

bool check_neg_cycle(std::vector<std::vector<int>> &adjmat, int n)
{
    std::vector<std::vector<int>> a(adjmat);

    for (int k = 1; k <= n; ++k)
    {
        for (int i = 1; i <= n; ++i)
        {
            for (int j = 1; j <= n; ++j)
            {
                if (a[i][j] > a[i][k] + a[k][j])
                {
                    a[i][j] = a[i][k] + a[k][j];
                }
            }
        }
    }
    for (int i = 1; i <= n; ++i)
    {
        if (a[i][i] < 0)
        {
            return true;
        }
    }
    return false;
}

int main()
{
    int tc;
    std::cin >> tc;
    int n, m, w;
    int s, e, t;

    while (tc--)
    {
        std::cin >> n >> m >> w;
        std::vector<std::vector<int>> adjmat(501, std::vector<int>(501, INF));
        for (int i = 0; i < m; ++i)
        {
            std::cin >> s >> e >> t;
            if (adjmat[s][e] > t)
            {
                adjmat[s][e] = t;
            }
            if (adjmat[e][s] > t)
            {
                adjmat[e][s] = t;
            }
        }
        for (int i = 0; i < w; ++i)
        {
            std::cin >> s >> e >> t;
            if (adjmat[s][e] > -t)
            {
                adjmat[s][e] = -t;
            }
        }
        for (int i = 1; i <= n; ++i)
        {
            if (adjmat[i][i] == INF)
            {
                adjmat[i][i] = 0;
            }
        }
        std::cout << (check_neg_cycle(adjmat, n) ? "YES" : "NO") << '\n';
    }
}