[ 백준 20303 ] 할로윈의 양아치 (C++) - 분리 집합, KnapSack

---

🔗 문제 링크

20303번: 할로윈의 양아치

---

💡 문제 풀이 및 해석

1. 첫 번째로 친구들의 집합을 만드는 것이 중요했다.
2. 친구관계도를 만들기 위해서 myFriend를 이용해서 i번의 친구를 vector로 저장한다.
3. 그럼 i번의 친구들의 친구들을 다시 모두 탐색한다. 단, 아직 친구 그룹이 형성되어 있다면 찾지 않는다. (이미 같은 그룹이기 때문)
4. 1N 번의 아이를 23번 과정을 반복해서 모든 그룹을 만들어준다.
5. 모든 그룹을 만들었다면, 그 그룹의 총 인원수와 총 사탕수를 구한다. (MakeGroup)
6. 이제 사람수, 사탕수 2개의 데이터로 압축했으니 이는 이제 냅색문제가 된다. (무게와 가치랑 같다)
7. 최고 무게에서의 답을 리턴하면 된다.

---

⭐️ 정답 코드 및 설명

#include<iostream>
#include<vector>
#include<queue>
#define endl "\n";

using namespace std;

int N, M, K; // 아이드 수, 친구 관계 수, 울음 공명 수
vector<int> dp;
vector<bool> visit;
vector<int> myCandy;
vector<vector<int>> myFriend;
vector<pair<int, int>> friendGroup; // 인원수, 사탕

void Input() {
    cin >> N >> M >> K;

    myCandy.push_back(-1); // 0 번 인덱스 소모
    myFriend = vector<vector<int>>(N + 1, vector<int>());
    visit = vector<bool>(N + 1, false);

    for (int i = 0; i < N; i++) {
        int candy; cin >> candy;
        myCandy.push_back(candy);
    }
    for (int i = 0; i < M; i++) {
        int a, b; cin >> a >> b;
        myFriend[a].push_back(b);
        myFriend[b].push_back(a);
    }
}

void MakeGroup() {
    queue<int> q;
    for (int i = 1; i <= N; i++) {
        int cnt = 0, value = 0; // 아이 수, 사탕 모음 수
        if (!visit[i]) {
            q.push(i);
            cnt++; // 나 추가
            value += myCandy[i]; // 내 사탕 수 추가
            visit[i] = true; // 그룹 확인
        }
        while (!q.empty()) {
            int cur = q.front(); q.pop();
            for (int j = 0; j < myFriend[cur].size(); j++) {
                int curFriend = myFriend[cur][j];
                if (!visit[curFriend]) {
                    visit[curFriend] = true;
                    q.push(curFriend); // 친구의 친구도 탐색해야함
                    cnt++; // 친구 추가
                    value += myCandy[curFriend]; // 친구의 사탕 수 추가
                }
            }
        }
        if (cnt > 0) {
            friendGroup.push_back({ cnt,value }); // 인원 수와 그들의 사탕 수를 그룹으로 생성
        }
    }
}

void sol() {
    dp = vector<int>(K + 1, 0);
    for (auto a : friendGroup) {
        int cnt = a.first, value = a.second;
        for (int i = K; i > 0; i--) {
            if (i - cnt < 1) break;
            // 현재 [인원수 - 내가 추가 인원수]의 위치에서 내 무게를 더한 것이 현재 무게보다 크다면 교체한다.
            if (dp[i - cnt] + value > dp[i]) dp[i] = dp[i - cnt] + value;
        }
    }
}
int main() {
    ios_base::sync_with_stdio(false); cin.tie(NULL);

    Input();
    MakeGroup();
    sol();

    cout << dp[K];

    return 0;
}

---

🤔 문제 후기

그룹화하는 것까지는 쉽게 되었는데, 갑자기 냅색을 어떻게 하지??? 하는 고민이 있었다. 그래서 그냥 이런 식이 아닐까? 하고 했는데, 우연하게 잘 맞아서 쉽게 해결한 문제인 것 같다. 작년에 풀었던 문제인데, 그때는 100ms였는데 이번에는 64ms에 풀려서 그래도 더 낫게 푼 것 같아서 기분은 좋았다 ㅎㅎ