BOJ : 12562 친구비

---

[BOJ 16562(G3)리뷰]

유니온 파인드를 응용하는 문제다. 친구 관계가 주어지고, 같은 관계 안에 있는 친구는 모두 친구로 삼을 수 있다. 이 때, 모든 친구들과 친구가 되기위한 최소비용을 구해야 한다.

유니온파인드 알고리즘에 최소 친구비를 추가하는 로직만 추가해주면된다. 친구 관계를 이어주는것은 일반적인 유니온파인드 과정과 똑같고, 모든 관계에대해 처리를 하고나면 같은 집합의 친구들끼리 묶일것이다. 이때, 각각의 집합의 최소비용을 구하여 모두 더한다음 그 값이 준석이가 가지고있는 돈으로 가능하다면 출력해주면 된다.

나는 기존 union함수에 최소 친구비를 추가하는 코드한줄을 추가했다. 매개변수로 들어온 a,b에 대하여 find함수를 돌리면 결국 그 친구가 속해있는 집합의 번호가 나오므로 굳이 일일히 모든 친구의 비용을 계산할 필요없이 집합을 대표하는 번호의 최소비용만 계속하여 갱신해주면 된다.

모든 관계를 처리한 후에 calc함수를 통하여 총 친구비의 합을 계산했다. 1부터 n까지돌며 , 같은 집합에 속해있는 친구비의 최소값을 더하고 같은 집합 대표번호를 방문처리하여 중복계산되지 않도록 처리했다.

-

처음엔 그냥 관계를 모두 묶어준 후에 bfs를 돌며 최소값을 찾으려했는데 좀 더 생각해보니 결국 같은 관계에 있는 친구비중 최소값만 필요한것이므로 그 부분만 처리하면 되겠다는 생각이들어 코드를 고쳤다.

/*
	21.01.24
	BOJ : 16562 친구비  (https://www.acmicpc.net/problem/16562)
	유니온 파인드
*/
#include <bits/stdc++.h>
using namespace std;

int p[10001];
int cost[10001];
bool vis[10001];
int n, m, k;


void init() {
	for (int i = 1; i <= n; i++) {
		p[i] = i;
	}
}

int find(int a) {
	if (p[a] == a) return a;
	p[a] = find(p[a]);
	return p[a];
}

void unionf(int a, int b) {
	a = find(a);
	b = find(b);
	cost[b] = min(cost[a], cost[b]);
	p[a] = b;
}

int calc() {
	int totalCost = 0;
	for (int i = 1; i <= n; i++) {
		int n = find(i);
		if (vis[n]) continue;
		totalCost += cost[n];
		vis[n] = 1;
	}

	return totalCost;
}

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

	cin >> n >> m >> k;
	init();
	for (int i = 1; i <= n; i++) {
		cin >> cost[i];
	}

	for (int i = 0; i < m; i++) {
		int a, b;
		cin >> a >> b;

		unionf(a, b);
	}
	
	int result = calc();

	if (k >= result) cout << result;
	else cout << "Oh no";
	return 0;
}