[백준] 16562 - 친구비

[문제링크]

16562번: 친구비

 

0. disjoint set 문제

 

1. 기존에 존재하는 학생들의 관계를 따라 set들을 합친다

 

2. 학생들을 친구비에 따라 정렬한다

 

3. 친구비가 낮은 순서로 친구맺기를 시도한다.

  - 해당 학생이 속한 집합의 root를 구해 이미 친구인 집합인지, 아닌지 판단한다

 

4. 모든 집단과 친구가 된 후, 금액이 k보다 크다면 실패

 

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.Comparator;
import java.util.StringTokenizer;

public class Main{
	public static void main(String[] args)throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

		StringTokenizer st = new StringTokenizer(br.readLine(), " ");
		n = pint(st.nextToken());
		int m = pint(st.nextToken());
		int k = pint(st.nextToken());
		int[][] cost=new int[n][2];
		boolean[] isFriend=new boolean[n];
		int friendMoney=0;
		
		init();
		st = new StringTokenizer(br.readLine(), " ");
		for (int i = 0; i < n; i++) {
			cost[i][0]=i;
			cost[i][1]=pint(st.nextToken());
		}
		for (int i = 0; i < m; i++) {
			st = new StringTokenizer(br.readLine(), " ");
			int x = pint(st.nextToken())-1;
			int y = pint(st.nextToken())-1;
			mergeGroup(x, y);
		}
		
		Arrays.sort(cost, new Comparator<int[]>() {
			@Override
			public int compare(int[] o1, int[] o2) {
				return o1[1]-o2[1];
			}
		});
		
		for (int i = 0; i < n; i++) {
			int root = getRoot(cost[i][0]);
			if(!isFriend[root]) {
				isFriend[root]=true;
				friendMoney+=cost[i][1];
			}
		}
		if(friendMoney>k)System.out.println("Oh no");
		else System.out.println(friendMoney);
		
	}
	static int n;
	static int[]parents;
	
	static void init() {
		parents=new int[n];
		for (int i = 0; i < n; i++) {
			parents[i]=i;
		}
	}
	
	static int getRoot(int x) {
		if(parents[x]!=x)return parents[x]=getRoot(parents[x]);
		return x;
	}
	
	static void mergeGroup(int x, int y) {
		parents[getRoot(y)]=getRoot(x);
	}
	
	static int pint(String s) {
		return Integer.parseInt(s);
	}
}

결과 화면