BOJ 16562 - 친구비

시간 제한	메모리 제한	제출	정답	맞은 사람	정답 비율
2 초	512 MB	3151	1385	1099	45.264%

문제

---

19학번 이준석은 학생이 N명인 학교에 입학을 했다. 준석이는 입학을 맞아 모든 학생과 친구가 되고 싶어한다. 하지만 준석이는 평생 컴퓨터랑만 대화를 하며 살아왔기 때문에 사람과 말을 하는 법을 모른다. 그런 준석이에게도 희망이 있다. 바로 친구비다!

학생 i에게 Ai만큼의 돈을 주면 그 학생은 1달간 친구가 되어준다! 준석이에게는 총 k원의 돈이 있고 그 돈을 이용해서 친구를 사귀기로 했다. 막상 친구를 사귀다 보면 돈이 부족해질 것 같다는 생각을 하게 되었다. 그래서 준석이는 “친구의 친구는 친구다”를 이용하기로 했다.

준석이는 이제 모든 친구에게 돈을 주지 않아도 된다!

위와 같은 논리를 사용했을 때, 가장 적은 비용으로 모든 사람과 친구가 되는 방법을 구하라.

입력

---

첫 줄에 학생 수 N (1 ≤ N ≤ 10,000)과 친구관계 수 M (0 ≤ M ≤ 10,000), 가지고 있는 돈 k (1 ≤ k ≤ 10,000,000)가 주어진다.

두번째 줄에 N개의 각각의 학생이 원하는 친구비 Ai가 주어진다. (1 ≤ Ai ≤ 10,000, 1 ≤ i ≤ N)

다음 M개의 줄에는 숫자 v, w가 주어진다. 이것은 학생 v와 학생 w가 서로 친구라는 뜻이다.

출력

---

준석이가 모든 학생을 친구로 만들 수 있다면, 친구로 만드는데 드는 최소비용을 출력한다. 만약 친구를 다 사귈 수 없다면, “Oh no”(따옴표 제거)를 출력한다.

접근

---

그룹화를 하는 문제이므로, 간단하게 Union-Find를 사용하면 된다.
각 그룹마다의 최소값을 찾아서 더하면 되는 문제다.
친구 사이를 엣지로 놓고 DFS로 풀어도 될 듯 하다.

풀이

---

우선 기본 Union-Find를 정의했다.
친구 사이를 입력 받을때마다 update를 해주었다.

입력이 끝나면, 1부터 순회하면서 각 그룹의 최솟값을 찾는다.
find를 사용해서, 각 인덱스의 부모를 확인한다.
그리고 visited 배열이 0이면 처음 그룹을 확인하는 것이므로, 그냥 더해주고 저장한다.
그렇지 않은 경우는 기존 값보다 작은 값일때만 업데이트해준다.

#include <bits/stdc++.h>
using namespace std;
#define ll long long int
#define FUP(i, a, b) for(int i = a; i <= b; i++)
#define FDOWN(i, a, b) for(int i = a; i >= b; i--)
#define MS(a, b) memset(a, b, sizeof(a))
#define ALL(v) v.begin(), v.end()
#define CIN(a) cin >> a;
#define CIN2(a, b) cin >> a >> b
#define CIN3(a, b, c) cin >> a >> b >> c
#define COUT(a) cout << a
#define COUT2(a, b) cout << a << ' ' << b
#define COUT3(a, b, c) cout << a << ' ' << b << ' ' << c
#define ENDL cout << '\n'
int dy[4] = { -1, 1, 0, 0 };
int dx[4] = { 0, 0, 1, -1 };

int N, M, K, a, b, parent[10001];
ll arr[10001], ans = 0, visited[10001];

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

void update(int x, int y)
{
	if (x > y) swap(x, y);
	x = find(x);
	y = find(y);
	parent[y] = x;
}


int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);

	CIN3(N, M, K);
	FUP(i, 1, N)
	{
		CIN(arr[i]);
		visited[i] = 0;
		parent[i] = i;
	}
	while (M--)
	{
		CIN2(a, b);
		update(a, b);
	}
	FUP(i, 1, N)
	{
		int p = find(i);
		if (visited[p] == 0)
		{
			ans += arr[i];
			visited[p] = arr[i];
		}
		else if(visited[p] > arr[i])
		{
			ans = ans - visited[p] + arr[i];
			visited[p] = arr[i];
		}
	} 
	ans <= K ? COUT(ans) : COUT("Oh no");

	return 0;
}