[백준 16562번 C++] 친구비

불쌍한 준석이를 도와주기위해 풀었던 문제...

준석이는 돈이 많다.

Union Find 알고리즘을 활용하여 푸는 문제로, 각각의 정점을 입력 받을 때 친구비가 가장 적게 드는 정점으로 부모노드를 지정하여 합집합을 만든 후 순차적으로 정점을 탐색하며 해당 정점의 부모노드가 탐색되지 않은 부모노드일 경우 check 한 이후 cost를 더해가면 된다.
다른 사람 풀이도 참고를 했는데, 결과적으로 중요한건 합집합을 모두 완성한 후 해당 노드가 탐색하지 않은 노드일 경우(같은 집합이 아닌 경우) 해당 cost를 더해주는 것이 중요하다. 나는 check 배열을 선언해 해당 정점이 탐색하지 않은 정점일 경우 cost에 더해주었다. 혹은 탐색하지 않은 정점일 경우 cost를 더해준 이후 0으로 합집합을 만들어주는 방식도 있다.
또한 친구비 배열이 정렬되지 않은 상태여도 알고리즘이 최소 비용을 찾을 수 있는 이유는 각 정점이 친구비가 적게 드는 정점으로 부모노드를 지정하기 때문이다.(따라서 어떤 정점을 탐색하든 가장 친구비가 적은 부모 정점을 반환한다)

각 정점간 distance가 아닌 해당 정점 그자체의 cost인 만큼 처음에 로직을 설계하기가 어려웠다.

#include <iostream>
#include <algorithm>

using namespace std;

int parent[10001];
int money[10001];
bool check[10001];

int getparent(int a) {
	if (parent[a] == a) return a;
	return parent[a] = getparent(parent[a]);
}

void Union(int a, int b) {
	a = getparent(a);
	b = getparent(b);

	if (money[a] < money[b]) parent[b] = a;
	else parent[a] = b;
}

int main() {
	int N, M, K,u,v;
	int answer = 0;
	cin >> N >> M >> K;
	
	for (int i = 0; i <= N; i++) parent[i] = i;
	for (int i = 1; i <= N; i++) cin >> money[i];
	
	for (int i = 0; i < M; i++) {
		cin >> u >> v;
		Union(u, v);
	}

	for (int i = 1; i <= N; i++) {
		int tmpnode = getparent(i);
		if (check[tmpnode]) continue;
		else {
			check[tmpnode] = true;
			answer += money[tmpnode];
		}
	}

	if (answer > K) cout << "Oh no" << "\n";
	else cout << answer << "\n";

}

준석아 다음엔 친구 사귈 돈으로 나한테 조금만 줘 ...