[백준] 16562번. 친구비 (java, union-find)

먼저 union-find 알고리즘으로 그룹을 연결해준다. 

vis배열 (해당 집합 그룹을 방문했는지)를 만든 다음 1번부터 n번까지 체크해준다.

 

이미 앞에서 방문한 집합에 속한 번호라면 pass

 

방문했던 집합에 속하지 않은 번호라면

1. 먼저 친구비를 내서 사귈 수 있는 친구인지 확인한다.

2. 해당 번호가 속한 집합의 vis를 true로 해주고 방문한 번호의 개수(cnt)를 1 증가시킨다.

3. 낸 비용만큼  answer를 증가시킨다. 

 

 

import java.util.Scanner;

//친구비
public class B_16562_Main {
	static int n,m,k;
	static int[] money;
	public static void main(String[] args) {
		Scanner sc=new Scanner(System.in);
		n=sc.nextInt();
		m=sc.nextInt();
		k=sc.nextInt();
		money=new int[n+1];
		for (int i = 1; i <= n; i++) {
			money[i]=sc.nextInt();
		}
		int[] parent=new int[n+1];
		for (int i = 1; i <=n; i++) {
			parent[i]=i;
		}
		for (int i = 0; i < m; i++) {
			int v=sc.nextInt();
			int w=sc.nextInt();
			union(parent,v,w);
		}

		int answer=0;
		int cnt=0;
		boolean vis[]=new boolean[n+1];
		for (int i = 1; i <=n; i++) {
			int group=findSet(parent,i);
			if(vis[group]) {//방문된 그룹
				cnt+=1;
				continue;
			}
			if(k-money[i]>=0) {
				vis[group]=true;
				cnt+=1;
				answer+=money[i];
				k-=money[i];
			}
		}
		if(cnt==n) {
			System.out.println(answer);
		}else {
			System.out.println("Oh no");
		}
		
	}
	private static int findSet(int p[],int x) {
		if(x==p[x])return x;
		return p[x]=findSet(p,p[x]);
	}
	private static void union(int p[],int x,int y) {
		x=findSet(p,x);
		y=findSet(p,y);
		if(x>y) {
			p[x]=y;
		}
		else {
			p[y]=x;
		}
		if(money[x]>money[y]) {
			money[x]=money[y];
		}else {
			money[y]=money[x];
		}
	}

}