[ 백준 1865 ] 웜홀 (C++)

백준의 웜홀(1865) 문제이다.

[ 문제 바로가기 ]

[ 문제풀이 ]

1) 이 문제는 한 출발점에서 출발해서 다시 출발점으로 돌아왔을 때, 시간이 되돌아 간 경우가 있는지 판단해야 하는 문제이다.

   즉, '웜홀'이라는 존재 때문에 비용이 음수인 경로가 존재하고, 이 때, 시간이 되돌아 갈 수 있는지를 판단해야 한다.

   본인은 이 문제를 '벨만 포드 알고리즘'으로 접근해 보았다.

   그래프에서 '음의 가중치가 존재' 하기 때문에, 최소비용을 구하는 알고리즘 중, 벨만포드 알고리즘을 생각했고,

   시간이 되돌아 갈 수 있는지 판단을 해야 하기 때문에, '음의 사이클이 존재하는지 판단' 하면 된다 생각해서 벨만포드

   알고리즘을 이용해서 접근하였다.

   아직 벨만포드 알고리즘에 대해서 잘 모른다면 아래의 글을 읽고 오도록 하자.

   [ 벨만포드 알고리즘 알아보기(Click) ]

2) 최종적인 출력은, 벨만포드 알고리즘으로 각 노드까지 가는데 걸리는 최소비용을 구한 후, 음의 사이클이 존재하는지

   판단할 때, 음의 사이클이 존재한다면 "YES"를 그게 아니라면 "NO"를 출력하도록 구현하였다.

   음의 사이클이 존재한다면, 특정 출발점으로 돌아왔을 때 시간이 되돌아 갈 수 있다는 의미이기 때문이다.

[ 소스코드 ]

#include<iostream>
#include<vector>
#include<cstring>
#include<string>
 
#define endl "\n"
#define MAX 510
#define INF 987654321
using namespace std;
 
int N, M, W;
int Dist[MAX];
string Answer;
vector<pair<pair<int, int>, int>> Edge;
 
void Initialize()
{
    for (int i = 1; i < MAX; i++) Dist[i] = INF;
    memset(Dist, -1, sizeof(Dist));
    Edge.clear();
}
 
void Input()
{
    cin >> N >> M >> W;
    for (int i = 0; i < M; i++)
    {
        int From, To, Cost;
        cin >> From >> To >> Cost;
        Edge.push_back(make_pair(make_pair(From, To), Cost));
        Edge.push_back(make_pair(make_pair(To, From), Cost));
    }
    for (int i = 0; i < W; i++)
    {
        int From, To, Cost;
        cin >> From >> To >> Cost;
        Edge.push_back(make_pair(make_pair(From, To), -Cost));
    }
}
 
void Solution()
{
    Dist[1] = 0;
    for (int i = 1; i <= N - 1; i++)
    {
        for (int j = 0; j < Edge.size(); j++)
        {
            int From = Edge[j].first.first;
            int To = Edge[j].first.second;
            int Cost = Edge[j].second;
 
            if (Dist[From] == INF) continue;
            if (Dist[To] > Dist[From] + Cost) Dist[To] = Dist[From] + Cost;
        }
    }
    for (int i = 0; i < Edge.size(); i++)
    {
        int From = Edge[i].first.first;
        int To = Edge[i].first.second;
        int Cost = Edge[i].second;
 
        if (Dist[From] == INF) continue;
        if (Dist[To] > Dist[From] + Cost)
        {
            Answer = "YES";
            return;
        }
    }
    Answer = "NO";
}
 
void Solve()
{
    int Tc; cin >> Tc;
    for (int T = 1; T <= Tc; T++)
    {
        Initialize();
        Input();
        Solution();
        cout << Answer << endl;
    }
}
 
int main(void)
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
 
    //freopen("Input.txt", "r", stdin);
    Solve();
 
    return 0;
}