[BOJ] 백준 1865 - 웜홀

문제 링크

1865번: 웜홀

지점(정점), 도로(무방향 간선), 웜홀(음의 가중치를 갖는 유방향 간선)으로 이루어진 그래프에서

출발을 하였을때보다 시간이 되돌아가 있는 경우(음의 사이클)가 존재하는지 찾는 문제이다.

 

Bellman-Ford 알고리즘으로 해결할 수 있었다. 해당 알고리즘은 아래 링크에서 확인 할 수 있다.

2021.04.06 - [Algorithm/Theory] - [Algorithm] Bellman-Ford Algorithm (벨만-포드 알고리즘)

[Algorithm] Bellman-Ford Algorithm (벨만-포드 알고리즘)

위 이론 설명에서는 인접 행렬(Adjacency Matrix)을 이용하여 그래프를 구현했지만,

메모리 제약상 이번 풀이에서는 인접 리스트(Adjacency List)를 이용하여 그래프를 구현했다.

 

풀이는 다음과 같다.

#include <iostream>
#include <utility>
#include <vector>

#define INF 2100000000

using namespace std;



int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	int tc;
	cin >> tc;
	while (tc--) {
		int n, m, w;
		cin >> n >> m >> w;
		//edge[start][index]={end,weight}
		vector<vector<pair<int, int>>> edges;
		//dist[start][end]=minimum distance
		vector<int> dist;
		edges.resize(n + 1);
		dist.resize(n + 1, INF);
		for (int i = 0; i < m; i++) {
			int s, e, t;
			cin >> s >> e >> t;
			edges[s].push_back(make_pair(e, t));
			edges[e].push_back(make_pair(s, t));
		}
		for (int i = 0; i < w; i++) {
			int s, e, t;
			cin >> s >> e >> t;
			edges[s].push_back(make_pair(e, -t));
		}
		bool isNegativeCycle = false;
		dist[1] = 0;
		// repeat for the number of vertexes
		for (int k = 0; k < n; k++) {
			// for all vertexes
			for (int i = 1; i <= n; i++) {
				// for all edges of vertex i
				for (int j = 0; j < edges[i].size(); j++) {
					int dest = edges[i][j].first;
					int weight = edges[i][j].second;	
					if (dist[dest] > dist[i] + weight) {
						dist[dest] = dist[i] + weight;
						if (k == n - 1) {
							isNegativeCycle = true;
						}
					}
				}
			}
		}
		if (isNegativeCycle) {
			cout << "YES\n";
		}
		else {
			cout << "NO\n";
		}
	}
	return 0;
}

Bellman-Ford 알고리즘은 (정점의 수)-1회 만큼 dist 배열의 갱신이 발생하지만,

위 풀이에서는 (정점의 수) 만큼 반복문을 진행한 다음

if (k == n - 1) {
	isNegativeCycle=true;
}

를 통해, 마지막 루프에도 dist 배열이 갱신된다면 해당 그래프가 음의 사이클을 갖고 있다는 것을 알수 있었다.