P.20303 할로윈의 양아치

코드

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

public class Main {

    static int n, m, k;
    static int[] candy;
    static ArrayList<Integer>[] graph;
    static boolean[] visited;

    static class Candy {
        int kids;
        int cnt;

        public Candy(int kids, int cnt) {
            this.kids = kids;
            this.cnt = cnt;
        }
    }

    static ArrayList<Candy> groupCandy = new ArrayList<>();

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        int[] line = Arrays.stream(br.readLine().split(" ")).mapToInt(Integer::parseInt).toArray();
        n = line[0]; m = line[1]; k = line[2];
        candy = Arrays.stream(br.readLine().split(" ")).mapToInt(Integer::parseInt).toArray();
        graph = new ArrayList[n];
        for (int i = 0; i < n; i++) graph[i] = new ArrayList<>();
        for (int i = 0; i < m; i++) {
            line = Arrays.stream(br.readLine().split(" ")).mapToInt(Integer::parseInt).toArray();
            graph[line[0] - 1].add(line[1] - 1);
            graph[line[1] - 1].add(line[0] - 1);
        }
        visited = new boolean[n];

        for (int i = 0; i < n; i++) {
            if (!visited[i]) {
                bfs(i);
            }
        }

        int[] dp = new int[k];
        int ans = 0;
        for (Candy candy1 : groupCandy) {
            for (int i = k - 1; i >= candy1.kids; i--) {
                dp[i] = Math.max(dp[i], dp[i - candy1.kids] + candy1.cnt);
                ans = Math.max(ans, dp[i]);
            }
        }

        bw.write(Integer.toString(ans));
        bw.flush();
    }

    private static void bfs(int target) {
        LinkedList<Integer> queue = new LinkedList<>();
        queue.add(target);

        int kid = 0, candyCnt = 0;
        while (!queue.isEmpty()) {
            Integer poll = queue.poll();

            if (!visited[poll]) {
                visited[poll] = true;
                kid++;
                candyCnt += candy[poll];

                for (Integer integer : graph[poll]) {
                    queue.add(integer);
                }
            }
        }

        groupCandy.add(new Candy(kid, candyCnt));
    }
}

코드 설명

bfs + knapsack 문제이다.

 

초기 아이디어는 캔디가 많은 순으로 정렬한 후, 해당 그룹의 캔디를 뺏을 수 있다면 바로 뺏는 것이었다.

그래서 방문하지 않은 아이일 경우 bfs를 수행하는 것이었는데 이 경우는 '그룹 자체'의 캔디가 많은지 확인하지 않는다는 문제점이 있었다.

따라서, bfs는 캔디가 많은 순으로 수행하지만 bfs의 결과를 보았을 때 그 그룹이 가장 많은 캔디를 갖고 있는 것은 아닐 수도 있다는 것이다.

이 문제를 해결하기 위해 bfs로 그룹을 찾고 knapsack으로 최상의 답을 찾았다.