백준 16562번: 친구비

 

 

Union-find를 활용하는 문제다

 

 

 

 

*** Union-find 개념 ***

https://gimmesome.tistory.com/34?category=1103655

[1주차] Union-find

 

 

 

 

 

 

 

 

1. 필요한 배열 2개 --> 부모노드가 담길 arr,  노드별 친구 비 A 
2. merge함수에서 두 노드의 A의 값(친구비)을 비교하고 더 싼 친구비를 가진 노드를 부모노드로 해서 합친다.
3. 트리가 몇개가 되든 각 트리의 루트노드(트리에서 가장 친구비가 가장 작음)들은 arr값으로 초깃값인 -1을 가진다.
4. arr배열값이 -1인 노드의 A값을 다 다더하여 k보다 작으면 친구가능, 크면 친구 불가능.

 

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

int arr[10001];
int A[10001];
int pay;

int findParent(int num) {
	if (arr[num] < 0)
		return num;
	int parent = findParent(arr[num]);
	arr[num] = parent;
	return parent;
}

void merge(int aParent, int bParent) {
	if (A[aParent] <= A[bParent]) {
		arr[bParent] = findParent(aParent);	// arr[bParent] = aParent; 가능
	}
	else {
		arr[aParent] = findParent(bParent);	//arr[aParent] = bParent; 가능
	}
}

int main(void) {
	ios_base::sync_with_stdio(0);
	cin.tie(0);	//cin 실행속도 향상

	int N, M, k;
	
	cin >> N >> M >> k;

	for (int i = 1; i <= N; i++) 
		cin >> A[i];

	for (int i = 1; i <= N; i++)
		arr[i] = -1;
	
	for (int i = 1; i <= M; i++){
		int a, b; 
		cin >> a >> b;  

		int aParent = findParent(a);
		int bParent = findParent(b);

		if (aParent == bParent)
			continue;

		merge(aParent, bParent);
	}
	
	for (int i = 1; i <= N; i++) {
		if (arr[i] < 0)
			pay += A[i];
	}

	if (pay <= k)
		cout << pay << endl;
	else
		cout << "Oh no" << endl;




	return 0;
}