[BOJ/백준 1865/C++] 웜홀

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

1865번: 웜홀

 

[문제 요약]

- 월드나라에는 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이다.

- 시간 제한 : 2초

- 메모리 제한 : 128MB

 

[문제 풀이]

문제를 처음 읽었을 떄 이게 뭔소리인가 했다.

 

제일 이해안됐던 말이 "다시 출발을 하였던 위치로 돌아왔을 때, 출발을 하였을 때보다 시간이 되돌아가 있는 경우가 있는지" 이거 였다.

 

곰곰히 생각해보니 간선의 가중치가 나타내는 값이 시간이고, 만약 이 가중치가 음의 가중치를 가질경우 이동할때 시간이 되돌아간다는 것을 의미했다.

 

문제에서 요구하는 것은 한 지점에서 출발하여 이동하다가 다시 출발 지점으로 돌아왔을때 시간이 되돌아가는 경우가 있는지여부를 구하는 것이다.

 

일단, 출발지점으로 다시 돌아온다는 것은 순환하는 길이 존재한다는 것이고, 시간이 되돌아 간다는 것은 돌아왔을때 비용이 음의 값을 가지면 된다는 것이다.

 

순환이 있는지 여부 + 음의가중치를 갖는 사이클을 찾는 방법으로는 벨만-포드 알고리즘(Bellman-Ford Algorithm) 방식이 있다. 

 

 

벨만-포드 알고리즘이란?

- 그래프에서 최단 경로 문제를 푸는 알고리즘이다. 이때 변의 가중치는 음수 일 수도 있다.

 

이 알고리즘의 가장 중요한 점은 간선의 가중치가 음수여도 가능하다는 점이다. 

 

최단 경로 문제를 푸는 알고리즘 중에 대표적으로 다익스트라 알고리즘이 있다. 다익스트라는 벨만-포드와 동일한 작업을 수행하지만 속도는 다익스트라가 더 빠르다. 하지만 다익스트라는 음수인 경우에는 처리할 수 없다.

 

벨만-포드 알고리즘의 가장 큰 특징은 "모든 경우의 수를  다 탐색해 가면서 최소비용을 찾는다" 이다.

 

동작원리로는

• 모든 간선들을 확인하면서, 출발점이 한번이라도 계산된 적이 있다면 도착점까지의 거리를 비교하여 갱신
• 위 과정을 N-1번 반복

여기서 N-1번 반복을 하는 이유는 만약 순환이 없을 경우 최악의 경우 최단경로를 구성하는 간선의 갯수가 N-1개일 것이다. 만약 여기서 한번도 위의 과정을 반복했을 때 값에 대한 갱신이 발생하면 최단경로에 방문하는 정점이 추가되었다는 것을 의미함으로 중복된 정점이 존재 할 것이다. 그렇다는 의미는 순환이 발생했다는 의미임으로 N-1번 반복 후 한번 더 시행했을때 갱신이 안 일어나면 순환이 없고, 일어나면 순환이 있다는 뜻이다.

 

위 과정을 이용하면 쉽게 문제를 풀 수 있다.

 

하지만 주의할 점이 모든 정점에 대해서 음의값을 갖는 사이클의 여부를 판단하면 너무 오래 걸린다. 하지만 사이클의 존재여부만을 판단하는건 임의의 한 정점에서 시작해도 판달 할 수 있다. 

 

이 아이디어를 사용하려면 기존에 벨만-포드 알고리즘 코드에서 계산된적이 없는 정점에 대해서는 지나쳤지만 이 방법에서는 확인을 해 주어야한다.

 

이유는 그림으로 확인할 수 있다.

 

대충 위와 같은 그래프가 있다고 가정할때 1번 정점에서 시작하여 벨만-포드를 적용시키면 3-4-5 사이클은 확인이 불가능해진다. 왜냐? 3-4-5는 애초에 계산될일이 없으니까.

 

하지만 계산여부를 무시하고 확인을하면 INF값을 갖는 사이클을 확인할 수 있는 것이다. 우리는 사이클의 여부만 판단하는거지 정확한 최단거리를 구할 필요는 없는 것이다.

 

#include <stdio.h>
#include <stdlib.h>
#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
#include <map>
#include <stack>
#include <queue>

int T;


using namespace std;

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

	cin >> T;
	while (T--)
	{
		int N, M, W;
		cin >> N >> M >> W;

		vector<pair<pair<int,int>,int>> edge_list;

		int s, e, c;
		for (int i = 0; i < M; i++)
		{
			cin >> s >> e >> c;
			edge_list.push_back({ {s,e},c });
			edge_list.push_back({ {e,s},c });
		}
		for (int i = 0; i < W; i++)
		{
			cin >> s >> e >> c;
			edge_list.push_back({ {s,e},-c });
		}
		vector<int> Dist(N + 1);
		for (int i = 1; i <= N; i++) Dist[i] = 987654321;

		Dist[1] = 0;
		for (int i = 0; i < N - 1; i++)
		{
			for (int j = 0; j < edge_list.size(); j++)
			{
				int start = edge_list[j].first.first;
				int end = edge_list[j].first.second;
				int cost = edge_list[j].second;

				if (Dist[end] > Dist[start] + cost) Dist[end] = Dist[start] + cost;
			}
		}

		bool flag = false;
		for (int j = 0; j < edge_list.size(); j++)
		{
			int start = edge_list[j].first.first;
			int end = edge_list[j].first.second;
			int cost = edge_list[j].second;

			if (Dist[end] > Dist[start] + cost)
			{
				flag = true;
				break;
			}
		}
		if (flag) cout << "YES\n";
		else cout << "NO\n";
	}
}

굳