20303 - 할로윈의 양아치 JAVA

1차원 냅색 + 그래프 개념이 포함된 문제이다.

첫번째 아이디어 : 한 명이 사탕을 뺏기면 친구들도 다 뺏긴다 -> BFS 탐색으로 친구들끼리 묶을 수 있다.

친구들끼리 묶어 하나의 입력으로 만든다. 그 후, 배낭 문제처럼 풀이한다.

예시를 들어보자.

각 사람마다 사탕의 개수를 갖고 있는 배열을 candies[]라고 하자.

N번째 사람을 생각해봤을 때, 해당 사람과 연결된 친구가 없을 경우 무게가 1이고 사탕의 개수가 candies[N]인 배낭 하나로 생각할 수 있다. (이 부분을 생각하지 못해서 틀렸었다.. 친구 관계가 없는 사람도 있음)

N번째 사람이 연결된 친구가 있을 경우, (자신 + 친구들의 수)만큼의 무게이고 사탕의 개수가 (candies[N] + candies[친구들의 idx])인 배낭 하나로 만들 수 있다.

++ 추가적으로 사람의 수와 친구들의 수가 꽤 많기 때문에, 2차원 배낭 문제로 해결하게되면 메모리를 많이 쓰게 된다. 따라서 K - 1부터 탐색해 배낭 문제를 풀이하는 방식을 채택하면, 메모리 사용량을 많이 줄일 수 있다.

배낭으로 사용할 클래스

    static class Bag {
        int weight;
        int candy;
        Bag(int weight, int candy) {
            this.weight = weight;
            this.candy = candy;
        }

        @Override
        public String toString() {
            return weight + " " + candy;
        }
    }

각 친구들과의 관계를 이용해 모두 배낭으로 만듦

-> adjList에는 N + 1만큼의 ArrayList를 가지고 있다.(1번부터 시작하기 위함)

public static ArrayList<Bag> findBags(int[] candies, ArrayList<ArrayList<Integer>> adjList) {
        // 가방 찾기
        ArrayList<Bag> retArr = new ArrayList<>();
        boolean[] visited = new boolean[candies.length]; // 이미 가방으로 만든 친구들을 제외하기위한 visited 배열
        for (int i = 1; i < adjList.size(); i++) {
            if (!visited[i]) {
                visited[i] = true;
                int candy = candies[i];
                int weight = 1;
                Queue<Integer> que = new ArrayDeque<>();
                que.offer(i);
                while (!que.isEmpty()) {
                    int target = que.poll();
                    for (int elem : adjList.get(target)) {
                        if (!visited[elem]) {
                            que.offer(elem);
                            visited[elem] = true;
                            weight++;
                            candy += candies[elem];
                        }
                    }
                }
                retArr.add(new Bag(weight, candy));
            }
        }
        for (int i = 1; i < visited.length; i++) { // 친구가 없는 사람들은 무게가 1인 배낭으로 꼭 변환해주어야 한다.
            if (!visited[i]) {
                visited[i] = true;
                retArr.add(new Bag(1, candies[i]));
            }
        }
        return retArr;
    }

 

입력 받기 + 배낭으로 만든 후 배낭 문제 풀이 형식으로 답안 출력

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());
        st = new StringTokenizer(br.readLine());
        ArrayList<ArrayList<Integer>> adjList = new ArrayList<ArrayList<Integer>>();
        int[] candies = new int[N + 1];
        adjList.add(new ArrayList<>());
        for (int i = 1; i <= N; i++) { // candies -> 해당 인간이 갖고 있는 사탕 수, adjList -> 친구 관계
            candies[i] = Integer.parseInt(st.nextToken());
            adjList.add(new ArrayList<>());
        }
        for (int i = 0; i < M; i++) {
            st = new StringTokenizer(br.readLine());
            int start = Integer.parseInt(st.nextToken());
            int end = Integer.parseInt(st.nextToken());
            adjList.get(start).add(end);
            adjList.get(end).add(start);
        }

        ArrayList<Bag> bags = findBags(candies, adjList); // K는 들 수 있는 가방 최대 무게
        int[] dp = new int[K]; // K 무게를 만든다. N번째 가방을 써서
        for (int bIdx = 0; bIdx < bags.size(); bIdx++) {
            Bag bag = bags.get(bIdx);
            for (int i = K - 1; i >= bag.weight; i--) {
                dp[i] = Math.max(dp[i], dp[i - bag.weight] + bag.candy);
            }
        }
        System.out.println(dp[K - 1]);
    }