[백준/Baekjoon] 20303 할로윈의 양아치 C++ :: DP & BFS

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

20303번: 할로윈의 양아치

---

1. Logic

- 친구관계를 bfs를 돌면서 친구관계를 만들어준다.

- Knapsack 알고리즘을 활용하여 사탕을 뺏을 수 있는 가치합의 최대값을 구해준다.

 

---

2. Code

#include<bits/stdc++.h>

using namespace std;

int n, m, k;

vector<int> vec[30001];
bool vis[30001];
int value[30001];
vector<pair<int, int>> ans;

int dp[30001][3001];

int solve(int idx, int cnt) {
    //그룹의 갯수
    for(int i = 1; i < ans.size(); i++) {
        //울린 애들 수
        for(int j = 1; j <= k; j++) {
            int curCost = ans[i].second;
            int curIdx = ans[i].first;

            if(curIdx > j)
                dp[i][j] = dp[i - 1][j];
            else
                dp[i][j] = max(dp[i - 1][j - curIdx] + curCost, dp[i - 1][j]);
        }
    }
    return dp[ans.size() - 1][k - 1];
}

void BFS(int start) {
    queue<int> pq;

    int save = value[start];
    int cnt = 1;

    pq.push(start);
    vis[start] = true;

    while(!pq.empty()) {
        int here = pq.front();
        pq.pop();
        
        for(int i = 0; i < vec[here].size(); i++) {
            int next = vec[here][i];
            if(vis[next]) continue;
            pq.push(next);
            vis[next] = true;
            cnt++;
            save += value[next];
        }
    }
    ans.push_back({cnt, save});
}

int main() {
    memset(dp, 0, sizeof(dp));
    ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    cin >> n >> m >> k;

    for(int i = 1; i <= n; i++) {
        int a;
        cin >> a;
        value[i] = a;
    }

    for(int i = 0; i < m; i++) {
        int start, end;
        cin >> start >> end;

        vec[start].push_back(end);
        vec[end].push_back(start);
    }
    ans.push_back({0, 0});
    for(int i = 1; i <= n; i++) {
        if(vis[i]) continue;
        BFS(i);
    }

    cout << solve(0, 0);
}

 

BottomUp방식

#include<bits/stdc++.h>

using namespace std;

int n, m, k;

vector<int> vec[30001];
bool vis[30001];
int value[30001];
vector<pair<int, int>> ans;

int dp[30001][3001];

int solve(int idx, int cnt) {
    if(idx >= ans.size()) return 0;
    int &ret = dp[idx][cnt];
    if(ret != -1) return ret;
    ret = 0;
    
    if(cnt + ans[idx].first < k) {
        ret = max(ret, solve(idx + 1, cnt + ans[idx].first) + ans[idx].second);
    }
    ret = max(ret, solve(idx + 1, cnt)); 
    
    return ret;
}

void BFS(int start) {
    priority_queue<int> pq;

    int save = value[start];
    int cnt = 1;

    pq.push(start);
    vis[start] = true;

    while(!pq.empty()) {
        int here = pq.top();
        pq.pop();
        
        for(int i = 0; i < vec[here].size(); i++) {
            int next = vec[here][i];
            if(vis[next]) continue;
            pq.push(next);
            vis[next] = true;
            cnt++;
            save += value[next];
        }
    }
    ans.push_back({cnt, save});
}

int main() {
    memset(dp, -1, sizeof(dp));
    ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    cin >> n >> m >> k;

    for(int i = 1; i <= n; i++) {
        int a;
        cin >> a;
        value[i] = a;
    }

    for(int i = 0; i < m; i++) {
        int start, end;
        cin >> start >> end;

        vec[start].push_back(end);
        vec[end].push_back(start);
    }

    for(int i = 1; i <= n; i++) {
        if(vis[i]) continue;
        BFS(i);
    }

    cout << solve(0, 0);
}

3. Feedback

해당 문제를 탑다운 방식 즉 재귀를 사용하여 풀었는데 시간초과가 났다. 바텀업 방식이랑 시간복잡도가 똑같기 때문에 통과 될 것이라고 생각했는데 계산을 더 하는 부분이 있는건지 확실히 모르겠다. 최적화를 해봐도 안되어서 조금 더 깊게 생각해 봐야겠다.

알고리즘 Solve 후 제가 생각한 Logic을 기록하는 개인 공부 블로그입니다.
내용 중 최적화가 가능한 부분등은 언제든지 댓글로 틀린 부분 및 피드백 주시면 공부 및 반영하겠습니다🧐