취미로 코딩하기

※ 글쓴이는 취미로 코딩을 익혀보는 사람이라 정확하지 않은 내용을 담고 있을 수 있다 ※

이번에 볼 문제는 백준 1865번 문제인 웜홀이다.
문제는 아래 링크를 확인하자.

www.acmicpc.net/problem/1865

이 문제는 음수 가중치 간선이 있는 방향그래프에서 음수 가중치인 사이클이 존재하는지 판단하는 문제이다.

"한 지점에서 출발을 하여서 시간여행을 하기 시작하여 다시 출발을 하였던 위치로 돌아왔을 때, 출발을 하였을 때보다 시간이 되돌아가 있는 경우"가 존재한다는 것은 결국 그 지점을 포함하는 음수 가중치인 사이클이 존재한다는 뜻이기 때문이다.

그래프에서 음수 가중치 사이클이 존재하는지를 판단하는 것은 Bellman-Ford(벨만-포드)알고리즘을 응용하여 해결할 수 있다. 음수 가중치 사이클이 없다면 두 노드 사이의 최단경로는 같은 노드를 두번 이상 포함하지 않으므로, 그 경로의 길이는 그래프의 총 노드개수 이하일 수밖에 없다는 점을 이용하는 것이다.

특정 한 점이 아닌 모든 점에 대하여 음수 가중치 사이클이 있는지 한번에 확인해야 효율적이므로, 일반적인 Bellman-Ford의 구현에 포함되어 있는 "이 점이 이미 방문한 점인지를 확인하는 과정"을 생략하는 것이 좋다. (주어진 그래프가 connected(연결그래프)라는 보장이 없기 때문이다.)

이외에도 Floyd-Warshall(플로이드-워셜) 알고리즘을 이용한 음수 가중치 사이클 판단법을 이용해도 이 문제를 해결할 수 있다.

아래는 제출한 소스코드이다.

#include <iostream>
using namespace std;

int dist[501];
int edges[5201][3];

void solve() {
	int N, M, W; cin >> N >> M >> W;

	int idx = 0;
	while (M--) {
		int S, E, T; cin >> S >> E >> T;
		edges[idx][0] = S, edges[idx][1] = E, edges[idx][2] = T;
		idx++;
		edges[idx][0] = E, edges[idx][1] = S, edges[idx][2] = T;
		idx++;
	}
	while (W--) {
		int S, E, T; cin >> S >> E >> T;
		edges[idx][0] = S, edges[idx][1] = E, edges[idx][2] = -T;
		idx++;
	}
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < idx; j++) {
			if (dist[edges[j][1]] > dist[edges[j][0]] + edges[j][2])
				dist[edges[j][1]] = dist[edges[j][0]] + edges[j][2];
		}
	}

	bool ans = 0;

	for (int j = 0; j < idx; j++) {
		if (dist[edges[j][1]] > dist[edges[j][0]] + edges[j][2])
			ans = 1;
	}

	if (ans) cout << "YES\n";
	else cout << "NO\n";
}

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);

	int T; cin >> T;
	while (T--) {
		solve();
	}
}