[C++ 알고리즘] 백준 1865번 : 웜홀

 


벨만포드

웜홀

풀이과정

벨만-포드 알고리즘을 이용해 해결하였다.

  1. 시간이 줄어들면서 출발 위치로 돌아오는 것 을 보고 벨만포드를 떠올리기
  2. 도로는 무방향이므로 양방향 간선 2개를 추가하기
  3. 웜홀의 가중치는 음수로 취급하기

이 세가지는 캐치했지만 놓친 부분이 있었다.


(1) 모든 정점에서 음의 사이클의 여부를 판단하였다.

vector<vector<int>> dist(n + 1, vector<int>(n + 1, MAX));
for (int k = 1; k <= n; k++) {
  dist[k][k] = 0;
  ...
}

대략 이런식으로 했더니 시간초과가 났고, 음의 사이클 여부는 임의의 한 정점에서 시작해도 판단할 수 있음을 깨달았다. 그래서 출발점이 무조건 1이라는 건가요 어떤 노드든 상관 없다는 건가요? 글을 읽어보면 된다.


(2) dist[s]==MAX 인 경우 지나치기

if (dist[s] != MAX && dist[e] > dist[s] + t) {
  dist[e] = dist[s] + t;
}

기존에 벨만포드를 풀 때 위와 같이 풀었어서 이번에도 저렇게 풀었으나, 자꾸 9%에서 틀렸습니다가 떠서 확인해보니 저 부분에서 문제가 있다는 것을 알았다. INF비교가 없어야 하는 이유가 뭘까요? 이 질문이 도움이 많이 되었다!


다음은 반례이다

1
2 0 1
2 2 1

정답 : YES

INF 비교를 추가하면 위 반례에서 NO가 뜰 것이다.


코드

#include <iostream>
#include <string>
#include <vector>

#define MAX 30'000'000

using namespace std;

int n, m, w;

struct edge {
	int s, e, t;
};

bool time_travel(int n, vector<edge> edges) {
	vector<int> dist(n + 1, MAX);

	int s, e, t;
	dist[1] = 0;
	for (int i = 1; i < n; i++) {
		for (int j = 0; j < edges.size(); j++) {
			s = edges[j].s;
			e = edges[j].e;
			t = edges[j].t;
			if (dist[e] > dist[s] + t) {
				dist[e] = dist[s] + t;
			}
		}
	}
	for (int j = 0; j < edges.size(); j++) {
		s = edges[j].s;
		e = edges[j].e;
		t = edges[j].t;
		if (dist[e] > dist[s] + t) {
			return true;
		}
	}

	return false;
}

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

	int TC;
	cin >> TC;

	int s, e, t;
	while (TC > 0) {
		cin >> n >> m >> w;

		vector<edge> edges;

		for (int i = 0; i < m; i++) {
			cin >> s >> e >> t;
			edges.push_back({ s,e,t });
			edges.push_back({ e,s,t });
		}
		for (int i = 0; i < w; i++) {
			cin >> s >> e >> t;
			edges.push_back({ s,e,-t });
		}

		if (time_travel(n, edges)) cout << "YES\n";
		else cout << "NO\n";

		TC--;
	}

	return 0;
}


:bookmark: REFERENCE
그래서 출발점이 무조건 1이라는 건가요 어떤 노드든 상관 없다는 건가요?
INF비교가 없어야 하는 이유가 뭘까요?