백준 16562: 친구비

문제 요약

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

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

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

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

문제 분류

• 자료 구조
• 그래프 이론
• 그래프 탐색
• 분리 집합

문제 풀이

각 친구들의 모임을 집합으로 파악하여, 각 집합별로 최소의 비용을 산정하는 문제이다. 각 집합을 유니온 파인드로 표현하였고, 루트 노드의 절댓값을 해당 집합의 최소 비용으로 하여 음수로 나타내었다. 즉, 2를 루트노드로 하는 친구 집합의 최소 비용은 p[2]가 된다.

이 문제에서는 친구를 1부터 세므로, 입력값에서 -1의 연산을 수행했고, 서로 다른 두 집합의 병합 시 해당 집합에서의 최소비용을 따져서 새 집합의 값으로 만들었다. 즉, a집합의 최소비용이 20(실제 저장시에는 음수여야 하므로 -20)이고, b집합의 최소비용이 30(역시 실제로는 -30)이라 가정하고, b집합을 a집합에 병합한다면, p[a]는 -20과 -30중 절대값이 더 작은 값, 그러나 이 값은 반드시 음수이므로 실제로는 더 큰 값을 저장하게 된다.

풀이 코드

#include <stdio.h>
#include <iostream>
#include <algorithm>

using namespace std;

int p[10000];
bool visited[10000];

int find(int n) {
	if (p[n] < 0) return n;
	p[n] = find(p[n]);
	return p[n];
}

void merge(int a, int b) {
	a = find(a);
	b = find(b);
	if (a == b) return;
	p[a] = max(p[a], p[b]);
	p[b] = a;
}

int main()
{
	int n, m, k, in, in2, res = 0;

	scanf("%d%d%d", &n, &m, &k);
	for (int i = 0; i < n; i++) {
		scanf("%d", &in);
		p[i] = -in;
	}
	for (int i = 0; i < m; i++) {
		scanf("%d%d", &in, &in2);
		merge(in - 1, in2 - 1);
	}
	for (int i = 0; i < n; i++) {
		int t = find(i);
		if (!visited[t]) {
			res += -(p[t]);
			visited[t] = true;
		}
	}
	if (res <= k) printf("%d", res);
	else printf("Oh no");
	return 0;
}