BOJ 백준 1865 : 웜홀

시작하면서

　이번 문제는 벨만 포드 알고리즘(Bellman-Ford Algorithm) 을 사용해 해결하는 문제이다.

BOJ 1865 - 웜홀

​

문제 이해

​ 이 문제는 벨만 포드 알고리즘을 사용해 해결하는 문제이다. 벨만 포드 알고리즘은 다익스트라 알고리즘과 거의 유사하지만, 다익스트라 알고리즘에서는 불가능한 음의 가중치가 있는 상황에서도 사용이 가능하다.

개념 추천 블로그

​ 이 문제가 벨만 포드 알고리즘 문제임을 인식하기 위해서는 문제에서 시간위 뒤로 가게 된다라는 부분이다. 시간이 뒤로 간다는 것은, 경로를 이동할때 음의 가중치를 갖는다는 말과 동일하게 해석할 수 있다. 또한, 벨만 포드 알고리즘에서는 음의 가중치 때문에 사이클을 돌게 되는 경우를 쉽게 찾을 수 있다. 그렇기에 벨만 포드 알고리즘을 사용해서 사이클을 찾기만 하면 문제는 해결된다.

​

해결

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
#include <math.h>

using namespace std;

class EdgeInfo
{
public:
    int destination, time;
};

#define MAX 99999999

bool IsCycleExist(const vector<vector<EdgeInfo>>& edgeInfoVector)
{
    vector<int> dist(edgeInfoVector.size(), MAX);

    dist[1] = 0;

    for (int i = 0; i < edgeInfoVector.size() - 1; i++)
    {
        for (int j = 1; j < edgeInfoVector.size(); j++)
        {
            for (int t = 0; t < edgeInfoVector[j].size(); t++)
            {
                if (dist[edgeInfoVector[j][t].destination] > dist[j] + edgeInfoVector[j][t].time)
                {
                    dist[edgeInfoVector[j][t].destination] = dist[j] + edgeInfoVector[j][t].time;
                }
            }
        }
    }

	for (int i = 1; i < edgeInfoVector.size(); i++)
	{
		for (int j = 0; j < edgeInfoVector[i].size(); j++)
		{
			if (dist[edgeInfoVector[i][j].destination] > dist[i] + edgeInfoVector[i][j].time)
			{
				return true;
			}
		}
	}

    return false;
}

int main()
{
    // sync off
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    // sync off

    int TC, N, M, W;

    cin >> TC;

    while (TC--)
    {
        cin >> N >> M >> W;

        vector<vector<EdgeInfo>> edgeInfoVector;
        edgeInfoVector.resize(N + 1);
        for (int i = 0; i < M; i++)
        {
            int start, destination, time;

            cin >> start >> destination >> time;

            edgeInfoVector[start].push_back({ destination, time });
            edgeInfoVector[destination].push_back({ start, time });
        }

        for (int i = 0; i < W; i++)
        {
            int start, destination, time;

            cin >> start >> destination >> time;

            edgeInfoVector[start].push_back({ destination, -time });
        }

        if (IsCycleExist(edgeInfoVector) == true)
        {
            cout << "YES\n";
        }
        else
        {
            cout << "NO\n";
        }
    }

    return 0;
}