백준 16562번 : 친구비 java

이 문제는 분리 집합을 이용하여 학생들이 서로 친구인지 아닌지 확인하면서 친구비를 지불하는 문제입니다.

이 문제에서는 한 무리의 학생들이 서로 친구일 경우 가장 적은 친구비를 주어도 되는 학생을 찾아 친구비를 지불하면 됩니다.

위 문제의 예제 1번은 다음과 같이 친구관계를 맺고 있습니다.

이 문제에서는 1, 3번 학생이 친구이고 2, 4, 5번 학생이 친구입니다.

따라서 이 그룹 중에서 각각 한 명씩만 친구가 되면 됩니다.

1번 학생의 친구비가 10이고 3번 학생의 친구비가 20이니 1번 학생에게 친구비를 지불해줍니다.

2번 학생의 친구비가 10이고 4번 학생의 친구비가 20, 5번 학생의 친구비가 30이니 2번 학생에게 친구비를 지불합니다.

따라서 20의 금액만 있다면 주어진 모든 학생들과 친구가 될 수 있습니다.

이를 활용하여 코드를 작성해보았습니다.

---

import java.io.*;
import java.util.*;

public class Main {
    static int[] parent;
    static int[] moneyArr;

    public static void main(String[] args) throws 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());

        parent = new int[N+1];
        for(int i = 1; i<=N; i++)
            parent[i] = i;
        moneyArr = new int[N+1];
        boolean[] visited = new boolean[N+1];

        st = new StringTokenizer(br.readLine());
        for(int i = 1; i<=N; i++)
            moneyArr[i] = Integer.parseInt(st.nextToken());

        while(M-->0){
            st = new StringTokenizer(br.readLine());

            int A = Integer.parseInt(st.nextToken());
            int B = Integer.parseInt(st.nextToken());

            union(A, B);
        }

        int moneySum = 0;

        for(int i = 1; i<=N; i++){
            int rootIdx = find(i);

            if(visited[rootIdx]){
                visited[i] = true;
                continue;
            }

            moneySum += moneyArr[rootIdx];

            visited[rootIdx] = true;
            visited[i] = true;
        }

        if(moneySum > K)
            System.out.println("Oh no");
        else
            System.out.println(moneySum);
    }
    static int find(int idx){
        if(parent[idx] == idx)
            return idx;
        else
            return find(parent[idx]);
    }
    static void union(int idx1, int idx2){
        int parent1 = find(idx1);
        int parent2 = find(idx2);

        if(moneyArr[parent1] >= moneyArr[parent2])
            parent[parent1] = parent2;
        else
            parent[parent2] = parent1;
    }
}