java 16562번 친구비 (백준)

import java.util.Scanner;

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

class Main {
	static int find(int p[], int x) {//노드가 속한 부분집합의 대표노드 구하기
		if(p[x] == x) return x;
		return p[x] = find(p, p[x]);
	}
	
	static 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;
	}
	
	public static final int M = 1000000000;
	
	public static void main(String[] args) {
		Scanner scan = new Scanner(System.in);
		int n, m, g, sum = 0;
		n = scan.nextInt();
		m = scan.nextInt();
		g = scan.nextInt();
		
		int p[] = new int[n+1];//노드의 부분집합의 대표노드를 담는 배열
		int G[] = new int[n+1];//친구비 배열
		int min[] = new int[n+1]; //특정 대표노드를 사기위한 최솟값을 저장하는 배열
		
		for(int i=1; i<=n; i++) {
			p[i] = i;//일단 노드의 부분집합의 대표노드를 자기자신으로 둔다
			min[i] = M;//최솟값을 저장하는 배열엔 일단 매우 큰 값을 넣는다.
			G[i] = scan.nextInt();//비용을 입력받는다.
		}
		
		for(int i=0; i<m; i++) {
			int a, b;//두명의 친구
			a = scan.nextInt();
			b = scan.nextInt();
			merge(p, a, b);//친구들의 부분집합을 합친다.
		}
		//모든사람 //사람이 속한 부분집합의 대표사람을 찾은 다음, 그 대표사람을 살 최솟값을 구한다.
		for(int i=1; i<=n; i++) if(min[find(p, i)] > G[i]) min[find(p, i)] = G[i];
        
        //부분집합의 대표 사람을 살 최솟값들의 합을 구한다.
		for(int i=1; i<=n; i++) if(min[i] < M) sum += min[i];
		
		if(sum <= g) System.out.print(sum);//위에서 구한 총합이 내가 가진돈보다 적거나 같다면
		else System.out.print("Oh no");//아니라면
		
		scan.close();
	}
}

 

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

 

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

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

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

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

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

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

 

https://h202.tistory.com/243

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

위의 c언어 코드를 java로 변환했습니다.

자세한 설명은 위 링크에 적혀 있습니다.