취미로 코딩하기

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

이번에 볼 문제는 백준 13905번 문제인 세부이다.
문제는 아래 링크를 확인하자.

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

가장 무게제한이 큰 다리부터 하나씩 차례대로 이용하여 섬들을 이어나가면서, 처음으로 s와 e가 연결되는 순간에 연결한 다리의 가중치를 출력하는 것으로 문제를 해결할 수 있다. 이것이 성립하는 이유는 최소 스패닝 트리(MST)를 탐색하는 크루스칼 알고리즘(Kruskal's algorithm)의 정당성 증명과정을 떠올리면 쉽게 이해할 수 있다.

모든 다리를 연결시켜도 s와 e가 연결되어있지 않다면 s에서 e로 이동할 수 없으므로 0을 출력해주자.

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

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

int N, M, S, E;
int uf[100001];

int findf(int x) {
	if (uf[x] == x) return x;
	return uf[x] = findf(uf[x]);
}

pair<int, pair<int, int>> edge[300000];

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

	cin >> N >> M >> S >> E;
	for (int i = 0; i < M; i++) {
		auto& e = edge[i];
		cin >> e.second.first >> e.second.second >> e.first;
	}

	sort(edge, edge + M);

	for (int i = 1; i <= N; i++) uf[i] = i;

	for (int i = M - 1; i > -1; i--) {
		auto& e = edge[i];
		int x = e.second.first, y = e.second.second;
		x = findf(x), y = findf(y);
		uf[y] = x;

		if (findf(S) == findf(E)) {
			cout << e.first;
			return 0;
		}
	}

	cout << 0;
}