c언어 16562번 친구비 (백준)

#include <stdio.h>
#define M 1000000000

//union find을 이용하면, 특정한 부분집합에 지불할 돈의 최솟값을 구할 수 있으며,
//특정한 부분집합들의 최소값을 합친 것이 모든 친구들을 사귈수 있는 돈의 최솟값이 된다!!!!!
//특정한 부분집합의 지불할 돈의 최솟값을 구하기 위해서는 그냥, 각각의 사람들의 대표노드를 구하고, 그 대표 사람을 사기(?)위한 돈의 최솟값을 구하면 된다.

int find(int p[], int x) { //노드가 속한 부분집합의 대표노드 구하기
	if(p[x] == x) return x;
	return p[x] = find(p, p[x]);
}

void merge(int p[], int x, int y) { //두개의 노드의 부분집합을 합치기
	x = find(p, x);
	y = find(p, y);
	if(x!=y) p[x] = y; //p[y] = x도 상관없습니다.
	return;
}

int main(void) {
	int n, m, g;
	scanf("%d %d %d", &n, &m, &g);

	int p[n+1]; //노드의 부분집합의 대표노드를 담는 배열
	int G[n+1]; //친구비 배열
	int min[n+1]; //특정 대표노드를 사기위한 최솟값을 저장하는 배열
	for(int i=1; i<=n; i++) { 
		p[i] = i; //일단 노드의 부분집합의 대표노드를 자기자신으로 둔다
		min[i] = M; //최솟값을 저장하는 배열엔 일단 매우 큰 값을 넣는다.
		scanf("%d", &G[i]); //비용을 입력받는다.
	}
	
	for(int i=0; i<m; i++) {
		int a, b; //두명의 친구
		scanf("%d %d", &a, &b);
		merge(p, a, b); //친구들의 부분집합을 합친다.
	}
	
	
	for(int i=1; i<=n; i++) {//모든사람
		if(min[find(p, i)] > G[i]) //사람이 속한 부분집합의 대표사람을 찾은 다음, 그 대표사람을 살 최솟값을 구한다.
		min[find(p, i)] = G[i];
	}
	
	int sum = 0; //부분집합의 최솟값의 총합
	for(int i=1; i<=n; i++) {
		if(min[i] < M) sum += min[i]; //부분집합의 대표 사람을 살 최솟값들의 합을 구한다.
	}
	
	if(sum <= g) printf("%d", sum); //위에서 구한 총합이 내가 가진돈보다 적거나 같다면
	else printf("Oh no"); //아니라면
}

 

풀이 : union(합집합) + find(찾기)

 

1. 노드의 부분집합의 대표노드를 담을 배열, 지불할 돈의 액수를 담을 배열, 특정한 노드를 사기위한 최소값을 담을 배열을 만든다

2. 노드의 부분집합의 대표노드는 일단 자기자신으로 하며, 특정한 노드를 사기위한 최소값을 담을 배열에 값을 넣어준다.

3. m만큼 서로 친구인 사람들을 입력 받은 뒤 두 노드의 집합을 합친다.

4. 모든 사람의 경우를 살피면서, 그 사람의 대표노드를 찾은 다음, 그 대표노드를 사기위한 비용의 최소값을 구한다.

5. 4.의 과정이 끝나면, 부분집합들의 대표노드를 사기위한 최소값들이 배열에 들어있을 것이다. 그 최솟값들을 모두 더한것이 모든 친구를 사귈 때 필요한 비용의 최솟값이 된다!

6. 5.에서 구한 최솟값이 내가 가지고 있던 돈의 액수보다 크면 "Oh no"을 출력, 그렇지 않으면, 최소비용을 출력하면 된다.

 

 

union find을 이용하면,

어떤 사람이 속한 부분집합의, 대표 사람(노드)를 알 수 있기에, 그 대표노드들을 구한 다음, 그 대표노드들을 사기위한 최솟값들을 구하고, 이 최솟값들을 합쳐주기만 하면 된다!

 

만약 1, 2, 3, 4 모두 대표 사람이 4라는 부분집합에 속해 있다면,

이 1, 2, 3, 4와 친구가 되기 위해선 이 넷중 한명만 친구가 되면 되며,

친구비의 최솟값은 이 네명중 가장 싼 사람하고 친구를 맺으면 된다!

 

이러면 부분집합에 속한 사람들과 친구가 되기 위한 최솟값을 구할 수 있으며,

이러한 부분집합들의 최솟값을 더하면!, 모든 친구들과 사귈수 있는 최솟값을 구할 수 있게 된다.

 

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

16562번: 친구비