[Baekjoon/C++] 20303번 - 할로윈의 양아치

[백준] Baekjoon Online Judge

문제로 이동

 

문제

Trick or Treat!!

10월 31일 할로윈의 밤에는 거리의 여기저기서 아이들이 친구들과 모여 사탕을 받기 위해 돌아다닌다. 올해 할로윈에도 어김없이 많은 아이가 할로윈을 즐겼지만 단 한 사람, 일찍부터 잠에 빠진 스브러스는 할로윈 밤을 즐길 수가 없었다. 뒤늦게 일어나 사탕을 얻기 위해 혼자 돌아다녀 보지만 이미 사탕은 바닥나 하나도 얻을 수 없었다.

단단히 화가 난 스브러스는 거리를 돌아다니며 다른 아이들의 사탕을 빼앗기로 마음을 먹는다. 다른 아이들보다 몸집이 큰 스브러스에게 사탕을 빼앗는 건 어렵지 않다. 또한, 스브러스는 매우 공평한 사람이기 때문에 한 아이의 사탕을 뺏으면 그 아이 친구들의 사탕도 모조리 뺏어버린다. (친구의 친구는 친구다?!)

사탕을 빼앗긴 아이들은 거리에 주저앉아 울고 K명 이상의 아이들이 울기 시작하면 울음소리가 공명하여 온 집의 어른들이 거리로 나온다. 스브러스가 어른들에게 들키지 않고 최대로 뺏을 수 있는 사탕의 양을 구하여라.

스브러스는 혼자 모든 집을 돌아다녔기 때문에 다른 아이들이 받은 사탕의 양을 모두 알고 있다. 또한, 모든 아이는 스브러스를 피해 갈 수 없다.

 

입력

첫째 줄에 정수 N, M, K가 주어진다. N은 거리에 있는 아이들의 수, M은 아이들의 친구 관계 수, K는 울음소리가 공명하기 위한 최소 아이의 수이다. (1≤N≤30 000, 0≤M≤100 000, 1≤K≤min{N,3 000})

둘째 줄에는 아이들이 받은 사탕의 수를 나타내는 정수 c1,c2,⋯,cN이 주어진다. (1≤ci≤10 000)

셋째 줄부터 M개 줄에 갈쳐 각각의 줄에 정수 a, b가 주어진다. 이는 a와 b가 친구임을 의미한다. 같은 친구 관계가 두 번 주어지는 경우는 없다. (1≤a,b≤N, a≠b)

 

출력

스브러스가 어른들에게 들키지 않고 아이들로부터 뺏을 수 있는 최대 사탕의 수를 출력한다.

 

---

풀이

#include <iostream>
#include <vector>
#include <queue>
using namespace std;

#define MAX 30001

struct Steal {
    int cnt = 0;    // 인원 수
    int candy = 0;  // 사탕 수
};

int N, M, K;
int child[MAX];         // 아이들이 받은 사탕의 양
bool visit[MAX];        // 방문 여부
int dp[MAX][3001];
vector<vector<int>> friends(MAX); // 친구 관계
vector<Steal> steal;    // 각 무리의 인원 수와 총 사탕 수

Steal bfs(int start);

// start가 포함된 무리의 인원 수와 사탕 수 구하기
Steal bfs(int start) {
    queue<int> q;
    Steal ss = { 0, 0 };

    q.push(start);
    visit[start] = true;

    while (!q.empty()) {
        int now = q.front();
        q.pop();

        ss.cnt++;
        ss.candy += child[now];

        for (int n : friends[now]) {
            if (!visit[n]) {
                q.push(n);
                visit[n] = true;
            }
        }
    }

    return ss;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);

    cin >> N >> M >> K;
    for (int i = 1; i <= N; i++) cin >> child[i];

    for (int i = 0; i < M; i++) {
        int a, b;
        cin >> a >> b;

        friends[a].push_back(b);
        friends[b].push_back(a);
    }

    steal.push_back({ 0, 0 });
    for (int i = 1; i <= N; i++) {
        if (!visit[i]) steal.push_back(bfs(i));
    }

    // 스브러스가  뺏을 수 있는 최대 사탕의 수 구하기
    for (int i = 1; i < steal.size(); i++) {
        int cnt = steal[i].cnt;
        int candy = steal[i].candy;

        for (int j = 0; j <= K; j++) {
            if (cnt > j)
                dp[i][j] = dp[i - 1][j];
            else
                dp[i][j] = max(dp[i - 1][j - cnt] + candy, dp[i - 1][j]);
        }
    }

    // 출력
    cout << dp[steal.size() - 1][K - 1] << '\n';

    return 0;
}

 

// start가 포함된 무리의 인원 수와 사탕 수 구하기
Steal bfs(int start) {
    queue<int> q;
    Steal ss = { 0, 0 };

    q.push(start);
    visit[start] = true;

    while (!q.empty()) {
        int now = q.front();
        q.pop();

        ss.cnt++;
        ss.candy += child[now];

        for (int n : friends[now]) {
            if (!visit[n]) {
                q.push(n);
                visit[n] = true;
            }
        }
    }

    return ss;
}

 너비 우선 탐색으로 start가 포함된 무리의 총 인원 수와 사탕 수를 구해서 return하는 함수이다. 한 아이의 사탕을 뺏으면 그 아이의 친구의 것들도 모두 빼앗아야 하기에 각 무리들의 정보가 필요하다.

 

    steal.push_back({ 0, 0 });
    for (int i = 1; i <= N; i++) {
        if (!visit[i]) steal.push_back(bfs(i));
    }

 위의 함수로 구한 무리는 steal에 push_back하여 따로 저장한다.

 

    // 스브러스가 뺏을 수 있는 최대 사탕의 수 구하기
    for (int i = 1; i < steal.size(); i++) {
        int cnt = steal[i].cnt;
        int candy = steal[i].candy;

        for (int j = 0; j <= K; j++) {
            if (cnt > j)
                dp[i][j] = dp[i - 1][j];
            else
                dp[i][j] = max(dp[i - 1][j - cnt] + candy, dp[i - 1][j]);
        }
    }

    // 출력
    cout << dp[steal.size() - 1][K - 1] << '\n';

 dp로 스브러스가 아이들에게서 뺏을 수 있는 최대 사탕의 수를 구하고, 답을 출력하는 부분의 코드이다.