백준 1865 - 웜홀(C++)

문제

N개의 정점이 있고 M개의 방향성이 없는 간선과 W개의 방향성이 있는 그래프가 주어진다.

 

이때 W는 음수의 가중치를 가지고 있다.

 

어느 시작점이든 출발을 했을 때보다 시간이 더 적은 경우가 있으면 "YES" 없으면 "NO"를 출력하는 문제이다.

입력

첫 번째 줄에는 테스트케이스의 수 T가 주어진다.

 

두 번째 줄부터 T개의 테스트케이스가 차례로 주어진다. 각 테스트 케이스의 첫 번째 줄에는 정점의 수 N(1 <= N <= 500), 방향성이 없는 간선의 수 M, 방향성이 있는 간선 W가 주어진다.

 

그 다음 줄에는 M개의 줄 만큼 방향성이 없는 간선이 차례대로 주어지고 그 다음에는 W개의 줄 만큼 방향성이 있는 간선이 주어진다.

 

예제 입력

2
3 3 1
1 2 2
1 3 4
2 3 1
3 1 3
3 2 1
1 2 3
2 3 4
3 1 8

예제 출력

NO
YES

문제 해결

어디서 힌트를 얻을 수 있을까?

 

우선 정점, 간선, 가중치, 그리고 음수라는 키워드를 통해 이 문제는 벨만 포드 알고리즘을 활용하여 문제를 풀 수 있다는 것을 알 수 있었다.

 

출발점에서 출발 했을 때보다 시간이 되돌아 가는 경우는 즉, 0으로 세팅된 시작점의 거리 dist[S] 더 작은 음수가 나와야 한다는 것이다.

 

이 말은 다시 말해 계속해서 최단 경로가 갱신될 수 있다는 말이고 음수 싸이클이 존재하냐 안하냐를 판단하는 문제이다.

 

하지만 출발점이 명확하게 주어지지 않았기 때문에 방문하지 않은 노드를 체크하여 해당 노드만을 검사하는 방식으로 해야 최소한의 시간만 사용하여 문제를 해결할 수 있다.

코드

#include <iostream>
#include <cstring>
#include <vector>
#include <utility>

typedef std::pair<int, int> P;

int INF = 987654321;
long long dist[501];

int bellFord(std::vector<P >* adj, int N, int S)
{
	dist[S] = 0;
	bool minCircle = false;
	for (int i = 0; i < N; i++)	
	{
		for (int j = 0; j < N; j++)
		{
			for (auto& it : adj[j])
			{
				int there = it.first;
				int nCost = it.second;
				if (dist[j] != INF && dist[there] > dist[j] + nCost)
				{
					dist[there] = dist[j] + nCost;
					if (i == N - 1)
						minCircle = true;
				}
			}
		}
	}
	return minCircle;
}

void solve(void)
{
	int N, M, W;
	std::cin >> N >> M >> W;
	std::vector<P > adj[N];
	for (int i = 0; i < M; i++)
	{
		int X, Y, C;
		std::cin >> X >> Y >> C;
		adj[X - 1].push_back(P(Y - 1, C));
		adj[Y - 1].push_back(P(X - 1, C));
	}
	for (int i = 0; i < W; i++)
	{
		int X, Y, C;
		std::cin >> X >> Y >> C;
		adj[X - 1].push_back(P(Y - 1, -C));
	}
	bool flag = false;
	for (int i = 0; i < N; i++)
	{
		if (dist[i] == INF)
		{
			if (bellFord(adj, N, i))
			{
				flag = true;
				break;
			}
		}
	}
	if (flag)
		std::cout << "YES" << "\n";
	else
		std::cout << "NO" << "\n";
}

int main(void)
{
	int T;
	std::cin >> T;
	for (int i = 0; i < T; i++)
	{
		for (int i = 0; i < 201; i++)
			dist[i] = INF;
		solve();
	}
	return 0;
}

문제 출처

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

1865번: 웜홀

이론

https://deulee.tistory.com/16

벨만 포드 알고리즘(Bellman-Ford Algorithm)