문제

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

Trick or Treat!!

10월 31일 할로윈의 밤에는 거리의 여기저기서 아이들이 친구들과 모여 사탕을 받기 위해 돌아다닌다. 올해 할로윈에도 어김없이 많은 아이가 할로윈을 즐겼지만 단 한 사람, 일찍부터 잠에 빠진 스브러스는 할로윈 밤을 즐길 수가 없었다. 뒤늦게 일어나 사탕을 얻기 위해 혼자 돌아다녀 보지만 이미 사탕은 바닥나 하나도 얻을 수 없었다.

단단히 화가 난 스브러스는 거리를 돌아다니며 다른 아이들의 사탕을 빼앗기로 마음을 먹는다. 다른 아이들보다 몸집이 큰 스브러스에게 사탕을 빼앗는 건 어렵지 않다. 또한, 스브러스는 매우 공평한 사람이기 때문에 한 아이의 사탕을 뺏으면 그 아이 친구들의 사탕도 모조리 뺏어버린다. (친구의 친구는 친구다?!)

사탕을 빼앗긴 아이들은 거리에 주저앉아 울고
$K$명 이상의 아이들이 울기 시작하면 울음소리가 공명하여 온 집의 어른들이 거리로 나온다. 스브러스가 어른들에게 들키지 않고 최대로 뺏을 수 있는 사탕의 양을 구하여라.

스브러스는 혼자 모든 집을 돌아다녔기 때문에 다른 아이들이 받은 사탕의 양을 모두 알고 있다. 또한, 모든 아이는 스브러스를 피해 갈 수 없다.

입력
첫째 줄에 정수
$N$,
$M$,
$K$가 주어진다.
$N$은 거리에 있는 아이들의 수,
$M$은 아이들의 친구 관계 수,
$K$는 울음소리가 공명하기 위한 최소 아이의 수이다. (
$1 \leq N \leq 30\ 000$,
$0 \leq M \leq 100\ 000$,
$1 \leq K \leq \min\left\{N, 3\ 000\right\}$)

둘째 줄에는 아이들이 받은 사탕의 수를 나타내는 정수
$c_1, c_2, \cdots, c_N$이 주어진다. (
$1 \leq c_i \leq 10\ 000$)

셋째 줄부터
$M$개 줄에 갈쳐 각각의 줄에 정수
$a$,
$b$가 주어진다. 이는
$a$와
$b$가 친구임을 의미한다. 같은 친구 관계가 두 번 주어지는 경우는 없다. (
$1 \leq a, b \leq N$,
$a \neq b$)

출력
스브러스가 어른들에게 들키지 않고 아이들로부터 뺏을 수 있는 최대 사탕의 수를 출력한다.

예제 입력 1
10 6 6
9 15 4 4 1 5 19 14 20 5
1 3
2 5
4 9
6 2
7 8
6 10
예제 출력 1
57

예제 입력 2
5 4 4
9 9 9 9 9
1 2
2 3
3 4
4 5
예제 출력 2
0

접근

한 아이의 사탕을 뺏으면 그 아이 친구들의 사탕도 모두 뺏어야 하기 때문에 친구로 연결되어 있는 관계인 경우 하나의 집합으로 보면 된다. 유니온 파인드를 사용해 집합을 나누고, 각 집합에 속해 있는 친구의 수와 빼앗게 되는 사탕 수의 합을 구해주었다.
그리고 나서 K명 미만에게 뺏을 수 있는 사탕 개수의 최댓값을 구하면 되는데, 완전 탐색을 하면 시간 초과가 난다.
K - 1을 가방 크기라고 생각하고 각 집합에 '속해 있는 친구 수'를 물건의 무게, '사탕의 수'를 물건의 가치라고 생각하면 0-1 knapsack 문제임을 알 수 있다.

구현

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

class Main {
    static int N;
    static int M;
    static int K;
    static int[] c;
    static int[] parent;
    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());
        c = new int[N + 1];
        parent = new int[N + 1];
        st = new StringTokenizer(br.readLine());
        for (int i = 1; i <= N; i++) {
            c[i] = Integer.parseInt(st.nextToken());
            parent[i] = i;
        }
        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);
        }
        
        Map<Integer, int[]> map = new HashMap<>(); // (속해 있는 아이 수, 사탕 수)
        for (int i = 1; i <= N; i++) {
            if (!map.containsKey(find(i))) {
                map.put(parent[i], new int[2]);
            }
            map.get(parent[i])[0]++;
            map.get(parent[i])[1] += c[i];
        }
        
        int length = map.size();
        int[] dp = new int[K];
        int[][] children = new int[length + 1][2];
        int idx = 1;
        for (int[] child : map.values()) {
            children[idx][0] = child[0];
            children[idx++][1] = child[1];
        }
        for (int i = 1; i <= length; i++) {
            for (int j = K - 1; j >= children[i][0]; j--) {
                dp[j] = Math.max(dp[j], children[i][1] + dp[j - children[i][0]]);
            }
        }
        
        System.out.println(dp[K - 1]);
    }

    private static int find(int x) {
        if (parent[x] == x) {
            return x;
        }
        return parent[x] = find(parent[x]);
    }

    private static void union(int a, int b) {
        a = find(a);
        b = find(b);
        if (a > b) {
            parent[b] = a;
        } else {
            parent[a] = b;
        }
    }
}