[백준] 16562 친구비

문제

19학번 이준석은 학생이 N명인 학교에 입학을 했다. 준석이는 입학을 맞아 모든 학생과 친구가 되고 싶어한다. 하지만 준석이는 평생 컴퓨터랑만 대화를 하며 살아왔기 때문에 사람과 말을 하는 법을 모른다. 그런 준석이에게도 희망이 있다. 바로 친구비다!

학생 i에게 Ai만큼의 돈을 주면 그 학생은 1달간 친구가 되어준다! 준석이에게는 총 k원의 돈이 있고 그 돈을 이용해서 친구를 사귀기로 했다. 막상 친구를 사귀다 보면 돈이 부족해질 것 같다는 생각을 하게 되었다. 그래서 준석이는 “친구의 친구는 친구다”를 이용하기로 했다.

준석이는 이제 모든 친구에게 돈을 주지 않아도 된다!

위와 같은 논리를 사용했을 때, 가장 적은 비용으로 모든 사람과 친구가 되는 방법을 구하라.

입력

첫 줄에 학생 수 N (1 ≤ N ≤ 10,000)과 친구관계 수 M (0 ≤ M ≤ 10,000), 가지고 있는 돈 k (1 ≤ k ≤ 10,000,000)가 주어진다.

두번째 줄에 N개의 각각의 학생이 원하는 친구비 Ai가 주어진다. (1 ≤ Ai ≤ 10,000, 1 ≤ i ≤ N)

다음 M개의 줄에는 숫자 v, w가 주어진다. 이것은 학생 v와 학생 w가 서로 친구라는 뜻이다. 자기 자신과 친구일 수도 있고, 같은 친구 관계가 여러 번 주어질 수도 있다.

출력

준석이가 모든 학생을 친구로 만들 수 있다면, 친구로 만드는데 드는 최소비용을 출력한다. 만약 친구를 다 사귈 수 없다면, “Oh no”(따옴표 제거)를 출력한다.

예제 입력 1

5 3 20
10 10 20 20 30
1 3
2 4
5 4

예제 출력 1

20

예제 입력 2

5 3 10
10 10 20 20 30
1 3
2 4
5 4

예제 출력 2

Oh no

풀이

유니온 파인드 방식으로 풀이하였다.

집합에 루트 부모를 넣기 위해 findP 를 원소마다 호출해줘야 하는게 포인트다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.HashSet;
import java.util.StringTokenizer;


public class Main {
    static int N; // 학생 수
    static int M; // 친구관계 수
    static int k; // 가지고 있는 돈
    static int[] parent; // 루트 부모 관리
    static int[] parent_fee; // 해당 인덱스 학생이 연결된 그룹(트리) 내 가장 작은 친구비

    static int findP(int x) {
        if (parent[x] != x) return parent[x] = findP(parent[x]);
        return parent[x];
    }

    static void union(int n1, int n2, int min_fee) {
        int p1 = findP(n1);
        int p2 = findP(n2);

        // 작은 인덱스쪽으로 합침
        if (p1 < p2) {
            parent[p2] = p1;
            parent_fee[p1] = min_fee;
        } else {
            parent[p1] = p2;
            parent_fee[p2] = min_fee;
        }
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken()); // 학생 수
        M = Integer.parseInt(st.nextToken()); // 친구 관계 수
        k = Integer.parseInt(st.nextToken()); // 가지고 있는 돈

        // parent 배열 초기화
        parent = new int[N + 1];
        for (int i = 1; i <= N; i++) parent[i] = i;

        // 학생별로 자신이 속한 그룹의 최소 친구 비용 기록(parent_fee 초기화)
        st = new StringTokenizer(br.readLine());
        parent_fee = new int[N + 1];
        for (int i = 1; i <= N; i++) {
            int f = Integer.parseInt(st.nextToken());
            parent_fee[i] = f;
        }

        // 친구 관계에 따라 union 진행, 이때 그룹 최소 비용도 관리(기록)해줘야 함
        for (int i = 0; i < M; i++) {
            st = new StringTokenizer(br.readLine());
            int ff = Integer.parseInt(st.nextToken());
            int sf = Integer.parseInt(st.nextToken());

            // 각각의 루트 정점의 트리(그룹)이 가지는 최소 친구 비용을 구함
            // -> 더 작은걸 합칠 때 parent_fee 에 기록함
            int f_min_fee = Math.min(parent_fee[findP(ff)], parent_fee[findP(sf)]);
            union(ff, sf, f_min_fee);
        }

        HashSet<Integer> set = new HashSet<>();
        for (int i = 1; i <= N; i++) {
            // parent 배열이 완전 납작함을 보장하지 않기에, 정점마다 루트 정점을 구해서 넣어줘야함
            // ex) parent 가 [1,2,1,2,1] 일때 하나의 트리로 형성은 되지만, parent 가 루트 정점으로 구성되지 않음
            // 따라서 비용을 구할때 1이 속한 그룹의 최소 친구비 + 2가 속한 그룹의 최소 친구비를 계산하게 됨
            set.add(findP(parent[i]));
        }

        int sum = 0;
        for (int p : set) {
            sum += parent_fee[p];
        }
        // 총합 친구비를 낼 수 있으면
        if (k >= sum) System.out.println(sum);
        // 총합 친구비를 낼 수 없는 경우
        else System.out.println("Oh no");
    }
}