웜홀

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

시간 제한	메모리 제한	제출	정답	맞힌 사람	정답 비율
2 초	128 MB	36111	8293	5117	21.896%

문제

때는 2020년, 백준이는 월드나라의 한 국민이다.

월드나라에는 N개의 지점이 있고 N개의 지점 사이에는 M개의 도로와 W개의 웜홀이 있다.

(단 도로는 방향이 없으며 웜홀은 방향이 있다.)

웜홀은 시작 위치에서 도착 위치로 가는 하나의 경로인데,

특이하게도 도착을 하게 되면 시작을 하였을 때보다 시간이 뒤로 가게 된다.

웜홀 내에서는 시계가 거꾸로 간다고 생각하여도 좋다.

시간 여행을 매우 좋아하는 백준이는 한 가지 궁금증에 빠졌다. 

한 지점에서 출발을 하여서 시간여행을 하기 시작하여 다시 출발을 하였던 위치로 돌아왔을 때,

출발을 하였을 때보다 시간이 되돌아가 있는 경우가 있는지 없는지 궁금해졌다.

여러분은 백준이를 도와 이런 일이 가능한지 불가능한지 구하는 프로그램을 작성하여라.

입력

첫 번째 줄에는 테스트케이스의 개수 TC(1 ≤ TC ≤ 5)가 주어진다.

그리고 두 번째 줄부터 TC개의 테스트케이스가 차례로 주어지는데 각 테스트케이스의 첫 번째 줄에는

지점의 수 N(1 ≤ N ≤ 500), 도로의 개수 M(1 ≤ M ≤ 2500), 웜홀의 개수 W(1 ≤ W ≤ 200)이 주어진다.

그리고 두 번째 줄부터 M+1번째 줄에 도로의 정보가 주어지는데 각 도로의 정보는 S, E, T 세 정수로 주어진다.

S와 E는 연결된 지점의 번호, T는 이 도로를 통해 이동하는데 걸리는 시간을 의미한다.

그리고 M+2번째 줄부터 M+W+1번째 줄까지 웜홀의 정보가 S, E, T 세 정수로 주어지는데

S는 시작 지점, E는 도착 지점, T는 줄어드는 시간을 의미한다.

T는 10,000보다 작거나 같은 자연수 또는 0이다.

두 지점을 연결하는 도로가 한 개보다 많을 수도 있다.

지점의 번호는 1부터 N까지 자연수로 중복 없이 매겨져 있다.

출력

TC개의 줄에 걸쳐서 만약에 시간이 줄어들면서 출발 위치로 돌아오는 것이 가능하면 YES, 불가능하면 NO를 출력한다.

예제 입력 1

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

예제 출력 1

NO
YES

출처

Olympiad > USA Computing Olympiad > 2006-2007 Season > USACO December 2006 Contest > Gold 1번

• 데이터를 추가한 사람: artichoke42, jh05013

알고리즘 분류

• 그래프 이론
• 벨만–포드

---

풀이 방법

풀이에 도움되는 글

https://www.acmicpc.net/board/view/72995 <- jh05013의 설명

이 문제에는 여러 우여곡절의 역사가 있습니다.

그래서인지 시작점이 어디라는 언급이 전혀 없는데도 인터넷에 있는 거의 모든 풀이가 1을 시작 정점으로 잡고,

원래 dist[v] != INF이 들어가야 최단거리가 제대로 구해지는데 이걸 오히려 빼버리는 데다가,

왜 이걸 빼야 정답을 받는지는 설명을 안 하고 있습니다.

1. 백준이가 출발을 어디서 하는가?

아무데서나 출발할 수 있습니다.

2. 왜 시작 정점을 1로 정해도 풀리는가?

방금도 언급했듯이 인터넷에 있는 거의 모든 풀이는 아래의 “코드 1″처럼 구현하고 있습니다.

그런데도 맞았습니다!!를 받는데, 그건 잘못된 구현이 오히려 이 문제에서는 올바른 풀이가 되어서 그렇습니다.

바로 dist[v] != INF를 검사하지 않는 것입니다. “코드 2″와 비교해 보세요.

코드 1은 “dist[v] == INF”를 “v를 방문하지 않았다”가 아니라 “v를 방문했고, 

v까지의 최단거리가 INF다”로 인식하고 있습니다.

그래서 이 코드는 이미 처음부터 모든 정점을 방문한 걸로 착각을 하게 되는데,

덕분에 음수 사이클이 어디에 있든 항상 도달이 가능하기 때문에 정답을 받습니다.

어차피 모든 정점을 처음부터 방문하니까, dist[1] = 0은 이 코드에서는 아무 의미가 없습니다.

dist[3] = 0을 하거나, 아예 이 줄을 빼도 맞습니다.

그렇다면 코드 1이 항상 코드 2보다 좋은 코드이냐? 그렇지 않습니다.

코드 1에서는 어떤 정점이 실제로 도달 가능한 정점인지 알 수 없기 때문에, 코드 1은 올바른 벨만 포드 구현이 아닙니다. 

(즉 v가 실제로 도달 불가능한 정점이더라도 dist[v] != INF일 수 있습니다.) 

단지 그 정보가 이 문제에서는 필요 없기 때문에 맞는 것뿐이고,

만약 문제가 “각 점까지의 최단거리를 구해라”였다면 코드 2처럼 하는 것이 좋습니다.

2-1. 코드 2는 왜 틀리는가?

아래의 “코드 2″처럼 구현했다면 오답 처리가 될 것입니다.

틀려야 되는 이유는 시작 정점으로부터 도달할 수 없는 음수 사이클을 못 찾기 때문입니다.

다시 말하면, 이렇게 구현했을 경우 한 점에서만 출발하면 안 됩니다.

2-2. 파이썬 float(‘inf’)

float(‘inf’)에 음수를 더해도 여전히 float(‘inf’)이기 때문에, 이 경우에는 거리 갱신이 이루어지지 않습니다.

그래서 이 경우는 코드 2와 똑같이 동작합니다.

2-3. 그럼 제 강의 자료가 틀린 건가요?

당장 위키피디아만 봐도 dist[v] != INF 같은 게 안 보이지만, 그렇다고 그 자료가 틀린 건 아닙니다.

일반적으로, 알고리즘 설명이나 수도코드에서 ∞ 같은 게 나오면 “아주 큰 수”가 아니라 진짜로 무한대입니다.

파이썬으로 치면 float(‘inf’)와 같습니다.

진짜로 무한대면 dist[v]가 ∞인지 여부와 관계없이 거리 갱신을 다 해도 상관없습니다.

실제로 구현할 때는 “무한히 큰 int”같은 건 없으니까,

도달을 아직 못 한 점에서는 거리 갱신을 안 하는 식으로 우회하는 것일 뿐입니다.

3. 두 번째 방법으로 구현했으면 어떻게 풀어야 하는가?

두 가지 방법이 있습니다.

• 시작 정점이 한 개일 필요는 없습니다. 모든 정점에서 “동시에” 시작할 수 있습니다.
  그러려면 거리 배열 전체를 INF가 아닌 0으로 초기화하고 벨만 포드를 돌리면 됩니다.
• 그래도 꼭 시작 정점이 단 하나였으면 좋겠다고 생각하신다면, N+1번째 “가짜 정점”을 만들어서
  나머지 모든 정점으로 가중치 0의 간선을 긋고, 시작 정점을 N+1로 잡으면 됩니다.
  그러면 모든 정점이 도달 가능하므로 음수 사이클이 어디에 있든 항상 찾을 수 있습니다.

코드 1
INF = 2000000000
모든 dist[v] = INF
dist[1] = 0
N-1번 반복:
  모든 v에 대해:
    모든 간선에 대해 최단거리 갱신
모든 v에 대해:
  모든 간선에 대해 최단거리 갱신
  갱신이 한 번이라도 일어났으면 true

===

코드 2
INF = 2000000000
모든 dist[v] = INF
dist[1] = 0
N-1번 반복:
  dist[v] != INF인 모든 v에 대해:
    모든 간선에 대해 최단거리 갱신
dist[v] != INF인 모든 v에 대해:
  모든 간선에 대해 최단거리 갱신
  갱신이 한 번이라도 일어났으면 true

통과된 코드

#include <iostream>
#include <vector>

using namespace std;

constexpr int MAXN = 501;

int disArr[MAXN];

int TC, N, M, W, S, E, T;

vector<pair<int, int>> graph[MAXN];

bool BellmanFord()
{
	cin >> N >> M >> W;

	vector<pair<int, int>> graph[MAXN];

	// 도로의 정보를 입력받는다.
	for (int i = 0; i < M; i++) {
		cin >> S >> E >> T;
		// 양방향
		graph[S].push_back(make_pair(E, T));
		graph[E].push_back(make_pair(S, T));
	}

	// 웜홀의 정보를 입력받는다.
	for (int i = 0; i < W; i++) {
		cin >> S >> E >> T;
		// 단방향
		graph[S].push_back(make_pair(E, -T));
	}

	// 출발은 어디에새 해도 상관이 없다.
	fill(disArr, disArr + MAXN, 0);

	// (모든 정점의 수 - 1) 번 확인한다.
	// N 번은 순환 체크
	for (int k = 1; k <= N; k++) {
		for (int i = 1; i <= N; i++) { // 시작 정점
			for (int j = 0; j < graph[i].size(); j++) {
				int v = graph[i][j].first; // 도착점
				int weight = graph[i][j].second; // 가중치
	
				// 시작 임시 배열의 가중치가 도착지의 가중치보다 크다면
				if (disArr[i] + weight < disArr[v]) {
					disArr[v] = disArr[i] + weight;

					// K == N 일때 새로 업데이트 된다는 의미
					if (k == N) return true; // 순환이 있음
					
				}
			}
		}
	}

	return false;
	// 순환이 없음
}

int main()
{
	ios_base::sync_with_stdio(false); // scanf와 동기화를 비활성화
	// cin.tie(null); 코드는 cin과 cout의 묶음을 풀어줍니다.
	cin.tie(NULL);
	std::cout.tie(NULL);

	cin >> TC;

	for (int i = 0; i < TC; i++) {

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

	}

	return 0;
}