C++) 백준 16562 친구비

16562번: 친구비

---

코드

 

#include <algorithm>
#include <iostream>
#include <map>

using namespace std;

map<int, int> parent;
int f[10005];
long long ans = 0;

int Find(int x) {
	if (x == parent[x]) return x;
	return parent[x] = Find(parent[x]);
}
void Union(int v, int w) {
	int pv = Find(v);
	int pw = Find(w);
	if (pv == pw) return;
	f[pv] < f[pw] ? parent[pw] = pv : parent[pv] = pw;
}
int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);

	int n, m, k;
	
	cin >> n >> m >> k;
	for (int i = 1; i <= n; i++) {
		cin >> f[i]; parent[i] = i;
	}

	while (m--) {
		int v, w;
		cin >> v >> w;
		Union(v, w);
	}
	for (int i = 1; i <= n; i++) {
		if (i == parent[i]) ans += f[i];
	}
	if (ans > k) cout << "Oh no";
	else cout << ans;
}

 

 

풀이

 

처음엔 다익스트라 방식으로만 고민, 문제 해결이 어려웠다.

분류가 분리 집합 문제임을 확인한 후, 분리 집합을 처음 접하였다.

 

분리 집합 (Union-Find)

• Union : 집합 여부 확인
• Find : 부모 확인 ( * 재귀를 통해 경로를 압축 )