[c++] 백준-1865 웜홀 (벨만포드)

1. 문제

2. 입 출력

3. 예제

4. 문제 해설

벨만 포드 알고리즘을 이용해서 (음의 가중치가 있기 때문이다! 웜홀) 음의 사이클이 존재하는 지를 판단하면 되는 문제였다. 

이 문제는 그러나 일반적인 벨만포드 알고리즘과는 다른 점이 두 가지가 존재한다. 

1. 웜홀이 아닌 도로의 경우 양방향 도로이다. 
2. 출발 노드가 정해져있지 않다. 

벨만포드 알고리즘은 모든 간선을 노드 수 -1 만큼 탐색하면서 한 노드로부터 다른 노드들의 최단 거리를 갱신해가는 알고리즘이다. 

 

원래는 간선의 시작 노드에 해당하는 노드를 방문한 적이 없다면 continue를 통해 넘기는 로직이 존재한다. 왜냐하면 시작 노드가 존재하기 때문에 시작노드로부터 간선이 도착한 적이 있어야 최단 경로를 계산할 수 있기 때문이다. 

 

하지만 이 문제에서는 시작점이 따로 정해져 있지 않다. 그러면 어떻게 해야할까? 

이 문제는 그리고 딱히 다른 노드로의 최단 거리를 구하라거나하는 요구사항도 존재하지 않는다. 

그저 음의 사이클이 존재하는 지 안하는 지만 판단하면 된다. 

 

일반적으로 벨만포드 알고리즘에서 음의 사이클이 존재하는 지의 여부는 N-1번 돌려본 후 한 번 더 돌려 N번째 돌렸을 때 만약 거리배열이 갱신된다면 음의 사이클이 존재하는 것이다. 

 

음의 사이클이 존재하지 않는 경우 시작 노드를 제외한 N-1번을 돌렸을 때 모든 최단 거리가 갱신되기 때문이다. 

 

따라서 위의 알고리즘을 이용해 음의 사이클을 판단하기로 했다. 

 

그렇다면 시작노드가 정해져있지 않다면 어떻게 될까?

맨 처음 dist 배열은 무한대로 초기화되어 있고 

간선을 기준으로 만약

dist[edge[j].end] > dist[edge[j].start] + edge[j].cost  

의 로직을 만족한다면 즉 간선의 끝 노드가 갖고 있는 거리가 간선 시작노드에 간선 cost를 더한 거보다 크다면 이 간선을 통해 이동하는 것이 더 이득이므로 (최단 거리로 이동할 수 있으므로) dist배열을 초기화해준다. 

 

그리고 이것은 시작 노드가 존재할 경우 이미 그 노드를 방문했을 경우에만 진행한다. 

 

하지만 이 문제에서는 따로 시작노드가 정해져있지 않으므로 그 노드를 방문했을 경우에만 진행하는 로직은 사라져야한다. 

그냥 돌리면 양의 cost를 갖는 간선들은 모두 반영이 되지 않을 것이고 

음의 cost를 갖는 간선들은 반영이 될 것이다. 

또한 N번째를 돌렸을 때도 갱신이 된다면 이것은 음의 사이클을 갖는 그래프라고 판단할 수 있다. 

 

따라서 코드는 다음과 같다. 

 

처음에는 시작노드를 1에서 N을 다 넣어본 후 만약 음의 사이클이 존재한다면 YES를 출력했으나 이 코드는 91%에서 계속 시간초과가 나왔다. 벨만포드 알고리즘을 음의 사이클에 포함되는 노드가 시작점이 될 때까지 진행해야하기 때문이다. 

4. 코드 

#pragma warning (disable : 4996)

/*
	음의 가중치가 존재하는 벨만 포드 알고리즘 문제이다. 
	isNegCycle이라는 변수를 만들어

	간선을 기준으로 N-1번 반복해 최단 거리를 갱신하고
	N번째를 돌려 또 갱신된다면 음의 사이클을 갖는 그래프이다. 
*/
#include <cstdio>
#include <vector>
#define ll long long
#define INF 0x3f3f3f3f
using namespace std;
struct edge {
	int start;
	int end;
	int cost;
};
int TC; // 테스트 케이스 개수
int N, M, W; // 노드 개수 , 간선 개수, 웜홀 개수
ll dist[501];
bool BellmanFord(vector<edge> v) {
	bool isNegcycle = false;
	for (int i = 1; i <= N; i++) {
		dist[i] = INF;
	}// 배열 초기화
	//dist[s] = 0;
	for (int i = 1; i < N; i++) {
		for (int j = 0; j < 2 * M + W; j++) {
			if (dist[v[j].end] > dist[v[j].start] + v[j].cost) {
				dist[v[j].end] = dist[v[j].start] + v[j].cost;
			}
		}
	}
	for (int j = 0; j < 2 * M + W; j++) {
		if (dist[v[j].end] > dist[v[j].start] + v[j].cost) {
			dist[v[j].end] = dist[v[j].start] + v[j].cost;
			return true;
		}
	}
	return false;
}
void sol() {
	vector<edge> v;
	scanf("%d %d %d", &N, &M, &W);
	for (int i = 0; i < M; i++) {
		int s, e, t;
		scanf("%d %d %d", &s, &e, &t);
		v.push_back({ s,e,t });
		v.push_back({ e,s,t }); // 도로는 방향이 없다. 
	}
	for (int i = 0; i < W; i++) {
		int s, e, t;
		scanf("%d %d %d", &s, &e, &t);
		v.push_back({ s,e,-t }); // 웜홀은 줄어든다. 
	}
	
	if (BellmanFord(v)) {
		puts("YES");
		return;
	}
	else {
		puts("NO");
		return;
	}
	return;
}
int main() {
	scanf("%d", &TC);
	for (int i = 0; i < TC; i++) {
		sol();
	}
	return 0;
}