백준 16562 친구비 [JAVA]

16562번: 친구비

 

 

풀이 방법

이 문제는 가장 적은 비용으로 모든 사람과 친구가 되는 방법을 구하는 문제였습니다.

 

1) 친구가 아닌 경우 친구 사귀기

    이때! 친구비가 더 적은걸로 친구비 변경해주기

2) M번의 친구 사귀기가 끝나면 한명씩 확인하면서 친구비 계산

3) 준석이가 가진 돈으로 친구를 다 사귈 수 있는지 확인

 

 

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
 
public class Main_BJ_16562_친구비 {
    
    static int N,M,K;
    static int [] parents, friendFee;
    static boolean [] check;
 
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        
        st = new StringTokenizer(br.readLine());
        
        N = Integer.parseInt(st.nextToken()); //학생수
        M = Integer.parseInt(st.nextToken()); //친구관계수 
        K = Integer.parseInt(st.nextToken()); //가지고 있는 돈
        
        friendFee = new int[N+1];
        parents = new int[N+1];
        check = new boolean[N+1];
        
        for(int i=1;i<parents.length;i++) parents[i] = i;
        
        st = new StringTokenizer(br.readLine());
        for(int i=1;i<friendFee.length;i++) friendFee[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);
        }
        
        int friend=0, answer=0;
        for(int i=1;i<parents.length;i++) {
            int temp = find(i);
            if(check[temp]) {
                friend++;
                continue;
            }
            if(K-friendFee[i]>=0) {
                friend++;
                answer+=friendFee[i];
                K-=friendFee[i];
                check[temp] = true;
            }
            
        }
        System.out.println(friend==N?answer:"Oh no");
 
    }
    
    public static void union(int a, int b) {
        int aRoot = find(a);
        int bRoot = find(b);
        
        if(aRoot<bRoot) parents[bRoot] = aRoot;
        else parents[aRoot]= bRoot;
        
        if(friendFee[aRoot]<friendFee[bRoot]) friendFee[bRoot] = friendFee[aRoot];
        else friendFee[aRoot] = friendFee[bRoot];
    }
    
    public static int find(int x) {
        if(parents[x]==x) return x;
        return parents[x]=find(parents[x]);
    }
 
}