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

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

16562번: 친구비

 

전체 코드

#include <iostream>
using namespace std;	
int cost[10001];
int parent[10001];
bool visit[10001];
int N, M,k;

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

void Union(int a, int b)
{
	a = find(a);
	b = find(b);
	if (a != b)
	{
		if (cost[a] >= cost[b])
			parent[a] = b;
		else
			parent[b] = a;
	}
}
int main(void)
{
	cin >> N >> M>>k;
	for (int i = 1; i<= N; i++)
	{
		int c;
		parent[i]=i;
		cin >> c;
		cost[i] = c;
	}
	for (int i = 0; i < M; i++)
	{
		int a, b;
		cin >> a >> b;
		Union(a, b);
	}

	int res = 0;
	for (int i = 1; i <= N; i++)
	{
		int cur = find(i);
		if (!visit[cur]) {
			res += cost[cur];
			visit[cur] = true;
		}
	}

	if (res > k)
		cout << "Oh no";
	else
		cout << res;

}

 

알고리즘은

일단 친구인 애들끼리 Union-find 알고리즘으로 묶어준다.

여기서 묶어줄 때 부모는 비용이 작은 애들으로 만들어준다.

이제 각 무리를 돌면서 친구비를 내면 된다.

여기서 친구비는 무리 중 가장 비용이 작은 친구에게만 낸다.

( 이미 Union을 비용 기준으로 했기에 부모를 찾아 비용을 내자 )

 

 

 

void Union(int a, int b)
{
	a = find(a);
	b = find(b);
	if (a != b)
	{
		if (cost[a] >= cost[b])
			parent[a] = b;
		else
			parent[b] = a;
	}
}

Union할때 부모가 다르다면 비용이 작은 친구가 부모를 맡는다.

 

for (int i = 1; i<= N; i++)
{
	int c;
	parent[i]=i;
	cin >> c;
	cost[i] = c;
}
for (int i = 0; i < M; i++)
{
	int a, b;
	cin >> a >> b;
	Union(a, b);
}

N번까지의 부모를 자기 자신으로 초기화하고

비용도 입력받아 초기화시킨다.

그다음 친구를 입력받아 Union해준다.

 

int res = 0;
for (int i = 1; i <= N; i++)
{
	int cur = find(i);
	if (!visit[cur]) {
		res += cost[cur];
		visit[cur] = true;
	}
}

1부터 N까지 돌며 부모의 비용을 더해준다.

이미 방문했던 부모라면 비용을 추가하지 않는다.

 

if (res > k)
	cout << "Oh no";
else
	cout << res;

친구비를 냈더나 k보다 크다면 친구비를 모두 못 내는 거다.