백준 1865(웜홀)

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

1865번: 웜홀

운동하려고 노트북 켰다가 학교 학회의 갓 906bc의 답변을 받고 깨달았다. 그래서 지금 정리하지 않으면 내일 또 귀찮아 할까봐 지금 쓰게되었다. 

 

이 문제는 사이클이 존재하냐 안 하냐의 문제이다. 

 

과연 사이클은 어떻게 알 수 있을까?

다수 vs 다수 최단거리를 구하는 걸 두번하면 되지 않을까 생각을 한다. 

 

결론은 플로이드 와샬을 두번? 사용하면 어떨까. 

 

만약에 그러니깐, 최단 거리로 가려고 하는 경우이고, 음의 값일 때에만 사이클이 존재할 수 있다.

안 그러면 시간낭비니깐 왜 같은 곳을 또 돌아? 

 

플로이드 와샬로는 사실 안 풀어봤다.

 

그냥 벨만포드로 이해를 해보자 

 

벨만포드의 알고리즘은 1vs 다수로 가는 최단 거리구하는 알고리즘이다. 하지만 이 다익스트라 대신 알고리즘을 쓰는 이유는 음의 간선으로 인한 사이클의 유무를 파악하기 쉽기 때문이다. 

 

음 벨만포드 알고리즘은 dist[]를 모두 INF로 저장해놓고, 출발점만 0으로 집어넣고 dist를 구한다. 

그래서 정점-1 만큼 반복했을때 dist[]에 저장된 값이 최단거리이고,  한 번 더 진행을 하였을 때, 변화가 있는 값이 cycle이다. 

 

만약에 진짜로 cycle만 찾으려고 한다면? 

 

dist[]의 값은 전혀 쓸모가 없다. 중요한건 변화가 있냐 없냐이다. 그러므로 dist[]의 값은 아무렇게나 하고, 정점만큼 반복했을때에 사이클존재만 확인하면 된다. 

 

이해가 안되면 생각해보자 

 

dist[]의 출발점값을 설정하는 이유는 거리를 구하기 위해서이다. 사이클만 볼때에는 출발하는 지점이 어디건 상관도 없다. 계속 반복하면 된다 

 

 

나도 이 문제를 처음에 INF로 설정하고 일반적인 최단거리를 구하는 문제처럼 풀려고 했다. dist[from] == INF 면 continue 까지 포함시켜서 물론 오답. 

 

이 반례는 

 

1 

3 2 0

2 3 -1

3 2 -1

 

이걸로 확인해보자

#include<iostream>
#include<vector>
#include<cstring>
using namespace std;
#define MAX 510

int N, M, W, TC, INF = 987654321;
long long dist[MAX];
vector<pair<pair<int, int>, int> > road;


void belman() {
	for (int i = 1; i <= N; i++) {
		for (int j = 0; j < road.size(); j++) {

			int from = road[j].first.first;
			int to = road[j].first.second;
			int cost = road[j].second;

			if (dist[to] > dist[from] + cost) {
				if (i == N) {
					cout << "YES\n";
					return;
				}
				dist[to] = dist[from] + cost;
			}
		}
	}

	cout << "NO\n";
	return;
}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);

	cin >> TC;
	int S, E, T;
	while (TC--) {
		cin >> N >> M >> W;
		road.clear();
		road.resize(N + 1);
		for (int i = 0; i < M; i++) {
			cin >> S >> E >> T;
			road.push_back(make_pair(make_pair(S, E), T));
			road.push_back(make_pair(make_pair(E, S), T));
		}
		for (int i = 0; i < W; i++) {
			cin >> S >> E >> T;
			road.push_back(make_pair(make_pair(S,E) , -T));
		}
		belman();
	}
}

 

 

코드를 보면 dist[]에 대한 초기화가 전혀 없다.

 

case마다 dist[]값이 누적되어서 사용되는데도 문제가 없다. 

 

만약에 test case가 많이 커지면 갑자기 오버플로가 일어나서 오류가 날 수도 있겠지만 tc가 5길래 그냥 짰다. 

 

알고리즘이 어떤식으로 어떻게 작동하는지 잘 파악하고 문제풀자 괜히 이상한 짓 하지말고.