[백준] 20303번 : 할로윈의 양아치 - 자바(JAVA)

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

20303번: 할로윈의 양아치

 

문제 해석

스브러스는 사탕을 뺏으려고 한다.

이때 스브러스는 사탕을 뺏을 때 한 아이의 사탕을 뺏으면 그 아이 친구들의 사탕도 모조리 뺏어버립니다.

이때 K명 이상의 아이들의 뺏지 않으면서 최대로 뺏을 수 있는 사탕의 양을 구하세요

 

문제 풀이전 설계

거리에 있는 아이들의 수 N = 30,000

아이들의 친구 관계 수 M = 100,000

K = 3,000

 

 

1. DFS/ BFS /Union Find 어떤것을 쓰던 우선 친구 그룹을 지어줍니다.

 

2. 친구그룹별로 사탕의 개수와 , 연결되어있는 친구들의 수가 도출됩니다.

 

3. 이를 토대로 최대 몇 명을 뺏을 수 있는지 탐색합니다.

 

문제 풀이하면서

2번까지는 순조롭게 잘 되었습니다.

이후에 3번을 2중반복문을통해 하면 해결되겠지 하고 제출하니 2%에 틀렸습니다가 나옵니다.

 

곰곰이 생각해보니 단순히 2개로만 최댓값을 비교하면 안 됩니다.

만약 3개, 4개를 합쳐서 최댓값이 되는 경우를 생각해보면 오답이 나오는 이유를 알 수 있습니다.

 

따라서 0-1 배낭 문제처럼 값을 계속 기록해나가면서 최댓값을 경신해나가야 정답을 찾을 수 있습니다.

 

 

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

public class Main_20303_할로윈의양아치 {

    static List<SteelInfo> canSteel = new ArrayList<>();
    static List<ArrayList<Integer>> links = new ArrayList<>();
    static int[] childs;
    static boolean[] visited;
    static int N, M, K;

    static class SteelInfo {
        int sum;
        int childCount;

        public SteelInfo(int sum, int childCount) {
            this.sum = sum;
            this.childCount = childCount;
        }

        @Override
        public String toString() {
            return "SteelInfo{" +
                    "sum=" + sum +
                    ", childCount=" + childCount +
                    '}';
        }
    }

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

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

        for (int i = 0; i <= N; i++) {
            links.add(new ArrayList<>());
        }

        for (int i = 0; i < M; i++) {
            st = new StringTokenizer(br.readLine());
            int a = Integer.parseInt(st.nextToken());
            int b = Integer.parseInt(st.nextToken());
            links.get(a)
                 .add(b);
            links.get(b)
                 .add(a);
        }

        //입력끝, 양방향 연결그래프 생성

        visited = new boolean[N + 1];

        for (int i = 1; i <= N; i++) {
            if (visited[i]) {
                continue;
            }
            SteelInfo result = steelCandy(i);
            if (result.childCount < K) {
                canSteel.add(result);
            }
        }

        int size = canSteel.size();


        int[][] dp = new int[2][K];

        for (int i = 0; i < canSteel.size(); i++) {
            SteelInfo now = canSteel.get(i);
            int childCount = now.childCount;
            int sum = now.sum;

            for (int j = 0; j < K; j++) {
                if (j >= childCount && dp[0][j - childCount] + sum > dp[0][j])
                    dp[1][j] = dp[0][j - childCount] + sum;
                else
                    dp[1][j] = dp[0][j];
            }
            dp[0] = dp[1].clone();
        }
        System.out.println(dp[1][K - 1]);
        

    }

    private static SteelInfo steelCandy(int childIndex) {

        Queue<Integer> bfsQ = new LinkedList<>();
        bfsQ.add(childIndex);
        visited[childIndex] = true;

        int sum = 0;
        int count = 0;
        SteelInfo result = null;
        while (!bfsQ.isEmpty()) {

            Integer curIndex = bfsQ.poll();
            sum += childs[curIndex];
            count++;

            for (Integer cur : links.get(curIndex)) {
                if (visited[cur]) {
                    continue;
                }

                bfsQ.add(cur);
                visited[cur] = true;
            }
        }
        result = new SteelInfo(sum, count);

        return result;

    }
}