백준 20303번 할로윈의 양아치 - C++ 풀이

---

 

1. 각 연결요소에 속하는 노드의 개수와 사탕의 총합을 구해준다.
2. 각 연결요소를 물건으로 생각한다. (노드 개수 = 무게, 사탕의 총합 = 가치)
3. 배낭의 최대 용량이 K-1인 냅색 문제로 바꾸어 푼다.

 

1. 각 연결요소에 속하는 노드의 개수와 사탕의 총합을 구해준다.

 친구끼리는 모두 한꺼번에 사탕을 빼앗기게 되므로 개인이 아니라 친구집합 단위로만 의미가 있다. 각 아이를 노드, 친구관계를 간선으로 생각하면 친구집합은 그래프의 각 연결요소가 된다. 이제 DFS/BFS 혹은 유니온파인드를 사용하여 모든 연결요소를 구해주자. 이때 각 연결요소에 속하는 노드(아이)의 개수와 각 노드에 걸린 사탕의 총합도 구한다.

 

2. 각 연결요소를 물건으로 생각한다. (노드 개수 = 무게, 사탕의 총합 = 가치)

 이 문제는 주어진 한도 K내에서 최대의 가치(사탕)를 얻는 냅색 문제와 같다. 각 연결요소를 물건으로 생각하자. 제한 대상인 노드의 개수는 물건 무게로 생각하고, 연결요소 내 사탕의 총합은 가치로 생각한다.

 

3. 배낭의 최대 용량이 K-1인 냅색 문제로 바꾸어 푼다.

 이제 DP를 이용하여 냅색문제를 풀면 된다. 재귀방식의 DP를 사용했더니 시간초과가 나서 반복문 방식으로 풀어주었다.

---

#include <iostream>
#include <vector>
#include <string.h>

using namespace std;

const int MAX_N = 30'000;
const int MAX_K = 3'000;

struct CC {
    int cnt;    // 연결요소에 속하는 노드의 개수
    int sum;    // 속하는 모든 노드에 걸린 사탕 개수의 합
};

int N, M, K, CN;
int num_of_candy[MAX_N];
vector<int> adjs[MAX_N];
bool visited[MAX_N];
int w[MAX_N+1];
int v[MAX_N+1];

CC DFS(int curr) {
    visited[curr] = true;
    
    int cnt = 1;
    int sum = num_of_candy[curr];
    
    for (auto next: adjs[curr]) {
        if (!visited[next]) {
            auto temp = DFS(next);
            cnt += temp.cnt;
            sum += temp.sum;
        }
    }
    
    return {cnt, sum};
}

// 모든 연결요소를 찾는 함수
void findCC() {
    for (int i=0; i<N; i++) {
        if (visited[i]) continue;
        
        CN++;
        auto cc = DFS(i);
        w[CN] = cc.cnt;
        v[CN] = cc.sum;
    }
}

int findMaxNumOfCandy() {
    findCC();
    
    // dp[i][j]: K=j일 때, i번 연결요소까지 고려하여 뺏을 수 있는 사탕의 최대개수
    vector<vector<int>> dp(CN+1, vector<int>(K+1, 0));
    
    for (int i=1; i<=CN; i++) {
        for (int j=0; j<=K; j++) {
            // i번 연결요소를 선택하지 않는 경우
            dp[i][j] = dp[i-1][j];
            // i번 연결요소를 선택하는 경우
            if (w[i] < j) {
                dp[i][j] = max(dp[i][j], v[i] + dp[i-1][j-w[i]]);
            }
        }
    }
    
    return dp[CN][K];
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);

    cin >> N >> M >> K;
    for (int i=0; i<N; i++) {
        cin >> num_of_candy[i];
    }
    for (int i=0; i<M; i++) {
        int u, v;
        cin >> u >> v;
        u--; v--;
        adjs[u].push_back(v);
        adjs[v].push_back(u);
    }
    
    cout << findMaxNumOfCandy();
}