백준 1865 - 웜홀(C++)

문제 링크입니다. https://www.acmicpc.net/problem/1865

1865번: 웜홀

밸만포드 알고리즘을 이용해 푸는 문제입니다.

문제를 봤을 때, 다시 출발점으로 돌아왔을 때, 시간이 줄어들어 있으면(음의 값을 가지고 있다면) 되돌아 가면 됨으로 "YES" 아니면 "NO"를 출력하는 문제입니다.

 

해당 문제를 다익스트라 알고리즘을 이용해 풀 생각을 해봤지만, 웜홀을 통해 이동할 때는, 시간이 음의 값을 가집니다. 가중치가 음의 값을 가지고 있는 상황에서는 다익스트라를 사용하면 안됨으로 최소비용을 구하는 알고리즘 중 하나인 밸만 포드 알고리즘을 사용해야 했습니다.

 

밸만 포드 알고리즘에 대해 조금 설명을 한 뒤 문제를 풀겠습니다.

 

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

밸만 포드 알고리즘은 모든 경우의 수를 전부 탐색해 가면서 최소비용을 찾게 됩니다.

따라서 X번 정점에서 갈 수 있는 다른 모든 정점의 최소비용을 구할 수 있습니다.

비록 다익스트라 알고리즘보단 시간이 더 오래 걸리지만, 음의 가중치를 계산할 수 있기에 해당 문제에 사용하기에 적합하다고 할 수 있습니다.

(해당 알고리즘이 궁금하다면 해당 링크를 확인해주세요 https://yabmoons.tistory.com/365)

 

그래프를 통해 시간을 되돌아가 있는 경우를 찾을 수 있는 방법은 음의 사이클이 있는지를 확인하는 방법입니다.

vector에 저장되어 있는 선 전부를 N-1번 돌려서 각 정점에서 갈 수 있는 최소 비용을 구했습니다.

이때 vector를 한번 더 확인했을 때, 최소 비용이 또 나올 수 있다면? -> 시간을 되돌아갈 수 있다는 뜻입니다.

 

따라서 해당 경우에 "YES"를 출력해주고, 아니라면 "NO"를 출력해주면 됩니다.

 

자세한 것은 코드를 참고해주세요

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <vector>
#include <cstring>
#include <string>
#include <queue>
#include <stack>
#include <cmath>
#define INF 987654321

using namespace std;

int N, M, W;
int test_case;
int Distance[501];
typedef struct line {
	int x;
	int y;
	int cost;
}line;
vector<line> connect;

void reset_distance() {
	for (int i = 1; i <= N; i++) {
		Distance[i] = INF;
	}
	memset(Distance, -1, sizeof(Distance));
}

void Find_wormhole() {
	Distance[1] = 0;
	for (int i = 1; i < N; i++) {
		for (int j = 0; j < connect.size(); j++) {
			int x = connect[j].x;
			int y = connect[j].y;
			int cost = connect[j].cost;
			if (Distance[x] == INF) continue;
			if (Distance[y] > Distance[x] + cost) {
				Distance[y] = Distance[x] + cost;
			}
		}
	}
	for (int i = 0; i < connect.size(); i++) {
		int x = connect[i].x;
		int y = connect[i].y;
		int cost = connect[i].cost;
		if (Distance[x] == INF) continue;
		if (Distance[y] > Distance[x] + cost) {
			cout << "YES" << "\n";
			return;
		}
	}
	cout << "NO" << "\n";
}

int main()
{
	cin.tie(0);
	cout.tie(0);
	cin >> test_case;
	for (int i = 0; i < test_case; i++) {
		cin >> N >> M >> W;
		for (int j = 0; j < M; j++) {
			int X, Y, Cost;
			cin >> X >> Y >> Cost;
			connect.push_back({ X,Y,Cost });
			connect.push_back({ Y,X,Cost });
		}
		for (int j = 0; j < W; j++) {
			int X, Y, Cost;
			cin >> X >> Y >> Cost;
			connect.push_back({ X,Y,-Cost });
		}
		reset_distance();
		Find_wormhole();
		connect.clear();
	}
	return 0;
}

 

 

질문 및 조언 댓글 남겨주세요