[BOJ 9344 // C++] 도로

※ 글쓴이는 취미로 코딩을 익혀보는 사람이라 정확하지 않은 내용을 담고 있을 수 있다 ※

 

이번에 볼 문제는 백준 9344번 문제인 도로이다.
문제는 아래 링크를 확인하자.

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

9344번: 도로

 

각 테스트케이스 별로 그래프에서 특정 에지가 MST(최소 신장 트리)에 포함될 수 있는지 판별할 것을 요구하는 문제이다.

주어지는 그래프의 MST는 유일하지 않으므로 MST를 크루스칼 알고리즘(Kruskal's Algorithm), 프림 알고리즘(Prim's Algorithm)등으로 아무거나 하나 구해 대조하는 것만으로는 문제를 해결할 수 없다. 모든 에지의 가중치가 같은 완전그래프를 생각해 보면 이는 간단하게 이해할 수 있을 것이다.

 

이 문제를 해결하는 방법은 여러 가지가 있다. 이 글에서는 그 중 두 가지를 간략하게 소개한다.

 

1. 크루스칼 알고리즘(Kruskal's Algorithm)의 변형

크루스칼 알고리즘에서 각 에지를 살펴 MST에 추가할 수 있다는 것을 확인 후 해당 에지를 바로 MST에 추가하는 대신 같은 가중치의 에지들을 묶어 각각 MST에 추가할 수 있는지 따로 확인한 다음 그 에지 중 추가할 수 있는 에지들을 MST에 추가하는 방법이다.

 

2. 주어진 그래프의 MST를 구성하는 비용과 주어진 에지를 우선적으로 먼저 집어넣고 나머지 노드를 최소비용으로 합쳤을 때의 비용을 구한 다음 두 값이 같은지 대조

 

글쓴이는 1번 방법을 구현하여 문제를 해결했다.

 

아래는 제출한 소스코드이다.

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int T, N, M, P, Q;
int arr[10001];
int findf(int x) {
	if (arr[x] == x) return x;
	return arr[x] = findf(arr[x]);
}
vector<pair<int, pair<int, int>>> E;

void solve() {
	E.clear();
	cin >> N >> M >> P >> Q;
	if (P > Q) swap(P, Q);
	auto PP = make_pair(P, Q);
	while (M--) {
		int x, y, w; cin >> x >> y >> w;
		if (x > y) swap(x, y);
		E.emplace_back(make_pair(w, make_pair(x, y)));
	}
	sort(E.begin(), E.end());
	for (int i = 1; i <= N; i++) arr[i] = i;
	int old = -1; vector<pair<int, int>> tmp;
	for (auto &p : E) {
		if (old < p.first) {
			for (auto &pp : tmp) {
				int x = findf(pp.first), y = findf(pp.second);
				if (x != y) arr[y] = x;
			}
			old = p.first;
			tmp.clear();
		}
		int x = findf(p.second.first), y = findf(p.second.second);
		if (x != y) {
			if (p.second == PP) {
				cout << "YES\n";
				return;
			}
			tmp.emplace_back(p.second);
		}
	}
	cout << "NO\n";
}

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);

	cin >> T;
	while (T--) solve();
}