[백준] 친구비 16562 - java

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

16562번: 친구비

public class 친구비 {
	static int parents[];
	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		int N = Integer.parseInt(st.nextToken());
		int M = Integer.parseInt(st.nextToken());
		int k = Integer.parseInt(st.nextToken());
		int friendMoney[] = new int[N+1];
		parents = new int[N+1];
		for(int i=1; i<=N; i++) {
			parents[i] = i;
		}
		st = new StringTokenizer(br.readLine());
		for(int i=1; i<=N; i++) {
			friendMoney[i] = Integer.parseInt(st.nextToken());
		}
		for(int i=0; i<M; i++) {
			st = new StringTokenizer(br.readLine());
			int a = Integer.parseInt(st.nextToken());
			int b = Integer.parseInt(st.nextToken());
			union(a,b, friendMoney);
		}
		int sum = 0;
		for(int i=1; i<=N; i++) {
			if(parents[i] == i) {
				sum += friendMoney[i];
			}
		}
		if(k - sum < 0) {
			System.out.println("Oh no");
		}
		else {
			System.out.println(sum);
		}
		
	}

	private static void union(int a, int b, int[] friendMoney) {
		int rootA = find(a);
		int rootB = find(b);
		if(rootA != rootB) {
			if(friendMoney[rootA] > friendMoney[rootB]) {
				parents[rootA] = rootB; 
			}
			else {
				parents[rootB] = rootA;
			}
		}
	}

	private static int find(int a) {
		if(parents[a] == a) return a;
		return parents[a] = find(parents[a]);
	}
}

연결된 같은 집합을 찾아 그 집합의 최소비용을 가지고 푸는 문제입니다.

따라서 union-find를 이용하면 됩니다.

union할 때 부모의 친구비용이 더 적은쪽으로 부모를 설정하면 됩니다.

 

union 메서드 작성할 때 실수를 했었는데

if(rootA != rootB) {
    if(friendMoney[rootA] > friendMoney[rootB]) {
        parents[rootA] = rootB; 
    }
    else {
        parents[rootB] = rootA;
    }
}

rootA의 부모를 바꿔야되는데 a의 부모를 바꾸려해서 틀렸었습니다.