[ 백준 BOJ ] 20303 번 - 할로윈의 양아치 (C++)

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

20303번: 할로윈의 양아치

모든 아이로부터 bfs를 돌려 각 아이마다 엮여있는 아이의 수와 얻을 수 있는 캔디의 수를 구한다. 처음에 그리디 방식으로 캔디의 수가 제일 많은 아이 그룹부터 추가해주는 식으로 했다. 하지만 K가 5일 때 한 그룹의 아이 수가 4명이고 총 20개, 아이가 2명인 그룹이 캔디 15개씩 있으면 답으로 20을 내놓게 된다. 따라서 배낭 문제 알고리즘을 써야 최적의 답이 나온다.

#include <iostream>
#include <cmath>
#include <cstring>
#include <algorithm>
#include <memory.h>
#include <vector>
#include <queue>

#define endl '\n'
#define ll long long
#define pii pair<int, int>

using namespace std;

int N, M, K;
vector<int> edge[30001];
int candy[30001];
bool check[30001];
pii store[30000];

int ct;

bool customCompare(pii a, pii b){
    return a.second>b.second;
}

int bfs(int i){
    ct=0;
    queue<int> q;
    q.push(i);
    int sum=0;
    while(!q.empty()){
        int node = q.front();
        q.pop();
        if(check[node])
            continue;
        ct++;
        check[node]=true;
        sum+=candy[node];
        for(int j = 0; j<edge[node].size(); j++){
            q.push(edge[node][j]);
        }
    }
    return sum;
}

int dp[3000];

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    cin >> N >> M >> K; 
    for(int i = 1; i<=N; i++){
        cin>>candy[i];
    }
    int x, y;
    for(int i = 0; i<M; i++){
        cin>>x>>y;
        edge[x].push_back(y);
        edge[y].push_back(x);
    }
    for(int i = 1; i<=N; i++){
        store[i].second=bfs(i);
        store[i].first=ct;
    }
    sort(store+1, store+N+1, customCompare);
    // for(int i = 1; i<=N; i++){
    //     cout<<store[i].first<<" "<<store[i].second<<endl;
    // }
    // cout<<endl;
    for(int i = 1; i<=N; i++){
        if(store[i].first==0)
            break;
        for(int j = K-1; j>=1; j--){
            if(j-store[i].first>=0){
                dp[j]=max(dp[j], dp[j-store[i].first]+store[i].second);
            }
        }
    }
    cout<<dp[K-1]<<endl;
    return 0;
}