[백준] 16562: 친구비 - JAVA

in Algorithm on 자료 구조

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

풀이

k원의 예산으로 모든 사람과 친구가 되는 방법을 구해야 한다.

친구마다 각각 원하는 친구비가 주어지고, 해당 학생과 어떤 학생이 친구인지 주어진다.

다만, 친구의 친구는 친구이기 때문에 이를 이용해 최소한의 비용으로 친구가 되어야 한다.

따라서 주어진 친구들의 관계를 이용해 그룹을 지었다.

각 그룹에 한 번 씩만 친구비를 전달하면 모든 친구와 친구가 될 수 있다.

union 메서드를 이용해 그룹을 지어주었다. 이떄 그룹의 대표 번호는 친구비가 가장 적은 사람으로 저장해주었다.

그룹을 모두 지은 뒤, 친구비를 더해 계산해주었다.

메모리: 18320KB

시간: 220ms

언어: Java 11

코드

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

public class Main {
    static int[] group, price;

    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());

        group = new int[n + 1];
        price = new int[n + 1];
        st = new StringTokenizer(br.readLine());
        for (int i = 1; i <= n; i++) {
            group[i] = i;
            price[i] = Integer.parseInt(st.nextToken());
        }

        for (int i = 0; i < m; i++) {
            st = new StringTokenizer(br.readLine());
            int v = Integer.parseInt(st.nextToken());
            int w = Integer.parseInt(st.nextToken());

            union(v, w);
        }

        int sum = 0;
        boolean[] selected = new boolean[n + 1];
        for (int i = 1; i < n + 1; i++) {
            int num = find(group[i]);
            if (selected[num]) {
                continue;
            }
            selected[num] = true;
            sum += price[num];
        }

        if (k < sum) {
            System.out.println("Oh no");
        } else {
            System.out.println(sum);
        }
    }

    private static void union(int a, int b) {
        int pa = find(a);
        int pb = find(b);

        if (price[pa] < price[pb]) {
            group[pb] = pa;
        } else {
            group[pa] = pb;
        }
    }

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

}