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

문제

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

16562번: 친구비

---

문제 요약

N명의 학생이 있을 때, 각 학생들과 친구가 되기 위해 필요한 비용, 친구비가 주어진다.

 

현재 k원이 있을 때, 모든 학생과 친구가 되기 위한 최소 비용을 출력한다.

 

+ "친구의 친구는 친구다"를 이용하면,  모든 친구에게 친구비를 지불하지 않아도 된다.

---

코드

#include <iostream>

#define MAX_N 10000

using namespace std;

// 학생 수, 친구 관계 수, 가지고 있는 돈
int n, m, k;

// i번 학생와 친구가 되기 위한 비용
int cost[MAX_N + 1];

// uf[i] : i번 학생이 속한 그룹 번호
int uf[MAX_N + 1];

// min_cost[i] : i번 그룹 학생들과 친구가 되기 위한 최소 비용
int min_cost[MAX_N + 1];

// x번 학생의 그룹 번호 반환
int find(int x) {
	if (uf[x] == x) {
		return x;
	}

	uf[x] = find(uf[x]);
	return uf[x];
}

// x번 학생과 y번 학생의 그룹을 같게 하는 함수
void union_(int x, int y) {
	x = find(x);
	y = find(y);

	uf[x] = y;
}

int main() {
	// 입력
	cin >> n >> m >> k;

	// 그룹 번호 초기화
	for (int i = 1; i <= n; i++) {
		uf[i] = i;
	}

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

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

		cin >> a >> b;

		if (find(a) == find(b)) continue;

		union_(a, b);
	}

	// 그룹 내 최소 친구비 탐색
	for (int i = 1; i <= n; i++) {
		int group_num = find(i);

		if (min_cost[group_num] == 0) {
			min_cost[group_num] = cost[i];
		}
		else if (min_cost[group_num] > cost[i]) {
			min_cost[group_num] = cost[i];
		}
	}

	int res = 0;

	// 각 그룹의 최소 친구비의 합이 k원 이하인지 확인
	for (int i = 1; i <= n; i++) {
		if (min_cost[i] <= k) {
			res += min_cost[i];
			k -= min_cost[i];
		}
		else {
			cout << "Oh no";
			return 0;
		}
	}

	cout << res;
	return 0;
}

---

코드 설명

"친구의 친구는 친구다"라는 성질을  유니온 파인드를 통해 그룹이라는 단위로 표현한다.

 

각 그룹에서 가장 친구비가 작은 값들을 모두 지불할 수 있는지 확인한다.