백준 1865 - 웜홀

문제 설명

때는 2020년, 백준이는 월드나라의 한 국민이다. 월드나라에는 N개의 지점이 있고 N개의 지점 사이에는 M개의 도로와 W개의 웜홀이 있다. (단 도로는 방향이 없으며 웜홀은 방향이 있다.) 웜홀은 시작 위치에서 도착 위치로 가는 하나의 경로인데, 특이하게도 도착을 하게 되면 시작을 하였을 때보다 시간이 뒤로 가게 된다. 웜홀 내에서는 시계가 거꾸로 간다고 생각하여도 좋다.

시간 여행을 매우 좋아하는 백준이는 한 가지 궁금증에 빠졌다. 한 지점에서 출발을 하여서 시간여행을 하기 시작하여 다시 출발을 하였던 위치로 돌아왔을 때, 출발을 하였을 때보다 시간이 되돌아가 있는 경우가 있는지 없는지 궁금해졌다. 여러분은 백준이를 도와 이런 일이 가능한지 불가능한지 구하는 프로그램을 작성하여라.

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

 

---

 

 

 

 

 

 

제한 사항

---

 

 

 

 

 

 

풀이

문제를 요약하면, 주어진 그래프에서 음수 사이클이 존재하는지 판단하면 된다.

 

음수 사이클을 판단하는 방법은 벨만-포드 알고리즘을 이용하는 것이다.

벨만-포드 알고리즘은 N-1번의 반복을 통해 모든 정점의 거리를 업데이트하는 알고리즘이다.

일반적인 벨만-포드 알고리즘은 특정 노드에서 다른 모든 노드까지의 최단 거리를 구하는 알고리즘이지만, 해당 문제에서는 음수 사이클만 판정하면 된다.

 

음수 사이클을 판단하는 것은 간단하다.

벨만-포드 알고리즘은 N-1번 만을 반복하지만 반복이 끝나고 한 번 더 거리를 갱신해 보는 작업을 수행한다.

이때, 만약 줄어드는 거리가 있다면 음수 사이클이 있다는 뜻이다.

void bellman()
{
	vector<int> dist(N + 1, 987654321);
	dist[1] = 0;

	for (int i = 1; i < N; i++)
	{
		for (auto edge : edges)
		{
			int from = edge.start;
			int to = edge.end;
			int cost = edge.dist;

			if (dist[to] > dist[from] + cost)
			{
				dist[to] = dist[from] + cost;
			}
		}
	}

	for (auto edge : edges)
	{
		int from = edge.start;
		int to = edge.end;
		int cost = edge.dist;

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

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

여기서 의문이 들 수 있다.

1번 노드를 시작점으로 잡고 벨만-포드를 진행하는데 어째서 음수 사이클이 제대로 판정이 될까?

이유는 간단하다.

만약, 주어진 그래프의 컴포넌트가 2개 이상이라면 1번 노드로 부터 방문하지 못하는 노드가 있을 수 있다.

그로 인해, 올바른 거리를 구하지 못할 것이다.

하지만, 해당 문제는 음수 사이클 여부만 판단하면 된다.

1번 노드로 부터의 올바른 거리가 아니더라도 음수 사이클이 있다면 설정한 최댓값에서 조금씩 줄어드는 값으로 갱신이 될 것이다.

예를 들어, a, b, c라는 노드가 있고 b->c(3), c->b(-4)라는 간선이 있다고 해보자.

a에서 시작하여 방문할 수는 없지만 b와 c는 자신들의 사이클을 통해 N-1번 반복하며 초깃값(987654321)에서 조금씩 거리를 갱신하며 줄여나갈 것이다.

그리고 마지막으로 사이클 판단을 위해 거리를 갱신하는 과정에서도 마찬가지 일 것이다.

따라서, 음수 사이클을 판단할 수 있다.

---

 

 

 

 

 

전체 코드

#include <bits/stdc++.h>

using namespace std;

int T, N, M, W;
struct Edge
{
	int start;
	int end;
	int dist;
};

vector<Edge> edges;

void bellman()
{
	vector<int> dist(N + 1, 987654321);
	dist[1] = 0;

	for (int i = 1; i < N; i++)
	{
		for (auto edge : edges)
		{
			int from = edge.start;
			int to = edge.end;
			int cost = edge.dist;

			if (dist[to] > dist[from] + cost)
			{
				dist[to] = dist[from] + cost;
			}
		}
	}

	for (auto edge : edges)
	{
		int from = edge.start;
		int to = edge.end;
		int cost = edge.dist;

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

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

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

	cin >> T;

	while (T--)
	{
		cin >> N >> M >> W;
		edges.clear();

		for (int i = 0; i < M; i++)
		{
			int a, b, c;
			cin >> a >> b >> c;

			edges.push_back({ a,b,c });
			edges.push_back({ b,a,c });
		}

		for (int i = 0; i < W; i++)
		{
			int a, b, c;
			cin >> a >> b >> c;

			edges.push_back({ a,b,-c });
		}

		bellman();
	}
	
	return 0;
}

---