백준 11085번 : 군사 이동 - Union & Find

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

11085번: 군사 이동

문제를 처음 봤을 때

DFS로 경로를 돌면서 최소 너비를 저장해 

최대의 최소 너비를 구해주고 싶은 생각이 들지만

 

그렇게 DFS를 돌 경우 모든 경우를 다 탐색하기 때문에 시간초과가 나게 됩니다.

Union & Find 알고리즘을 이용해서 해결해야합니다.

 

문제에서 주어지는 간선을 내림차 순으로 정렬하고

간선의 노드마다 Union 해주면서 최소한 어떤 너비의 간선까지 Union해주어야

시작지점과 도착지점이 연결되는지 구해야합니다.

 

#include <bits/stdc++.h>
using namespace std;

int p, w;
int unf[1001];

int Find(int x) {
	if (unf[x] < 0) return x;

	return unf[x] = Find(unf[x]);
}

void merge(int x, int y) {
	x = Find(x);
	y = Find(y);
	if (x == y) return;
	unf[x] = y;
}

struct Edge {
	int a, b, c;
	bool operator<(const Edge& bb) const {
		return c > bb.c;
	}
};

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

	vector<Edge> v;
	memset(unf, -1, sizeof(unf));

	int st, end;
	cin >> p >> w;
	cin >> st >> end;
	for (int i = 0; i < w; i++) {
		int a, b, c;
		cin >> a >> b >> c;
		v.push_back({ a,b,c });
	}
	int ans = INT_MAX;
	sort(v.begin(), v.end());

	for (int i = 0; i < v.size(); i++) {
		merge(v[i].a, v[i].b);
		ans = min(ans, v[i].c);

		if (Find(st) == Find(end)) {
			cout << ans << '\n';
			return 0;
		}
	}


	return 0;
}

백준 11085번 Union & Find