백준 2213 트리의 독립집합 - 어떤놈인지까지 찾아야 하는 트리dp c++

문제 링크

www.acmicpc.net/problem/2213

2213번: 트리의 독립집합

풀이 아이디어

트리 dp 문제를 단계로 나눠보자면 1단계는 사회망 서비스 hqjang.tistory.com/104?category=913845 문제를 들 수 있다.

단순히 그 트리 내에서의 요구하는 값의 최댓값 혹은 최솟값을 찾아내면 되는 문제.

이 문제는 2단계 정도에 해당한다. 최댓값/최솟값을 찾고, 그 값을 이루는 노드들을 구해야 한다.

당연히 dfs를 이용한 트리의 재귀 탐색이 모두 끝난 후에, 최적값을 이루는 노드들을 구해낼 수 있으며

이는 별도의 함수를 이용해 탐색해야 한다.

 

트리dp 1단계에서도 늘 그래왔듯, 2차원 dp 배열을 만든다.

dp[][0]은 해당 노드를 독립집합으로 선택하지 않음, dp[][1]은 해당 노드를 독립집합으로 선택

함을 의미한다.

 

그다음은 해당 노드가 최적해에 포함되는지 아닌지 여부를 함수 'track'를 통해 찾아낸다.

해당 노드가 독립집합에 포함되어야 할시 state 값을 1(true)로, 아닐시 0(false)로 두고

tracking 여부를 다시 결정하는 방식으로 진행시키자.

 

void track(int prev, int cur, bool state){
    if(state){ // state==1, cur 노드가 독립집합에 포함되어야 된다는 뜻, child는 전부 빠져야 된다는 것
        ansvec.push_back(cur);
        for(auto child:edge[cur]){
            if (child==prev) continue;
            track(cur, child, 0);
        }
    }
    else{ //state==0, child 노드의 dp값을 보면서 들어 가는게 최대값을 만들게 하는지 안들어 가는게 최댓값을 만들게 하는지를 봐라.
        for(auto child:edge[cur]){
            if(child==prev) continue;
            if(dp[child][1]>=dp[child][0])
                track(cur, child, 1);
            else
                track(cur, child, 0);
        }
    }
}

 

코드

#include <bits/stdc++.h>
using namespace std;

int n;
int dp[10001][2]; //dp[][0]은 해당 노드를 독립집합으로 선택하지 않음, dp[][1]은 해당 노드를 독립집합으로 선택
int cost[10001];
vector<vector<int>> edge;
bool visited[10001];
vector<int> ansvec;

void dfs(int n){
    visited[n]=true;
    dp[n][1]= cost[n];
    for(int child: edge[n]){
        if(visited[child]) continue;
        dfs(child);
        dp[n][1] += dp[child][0];
        dp[n][0] += max(dp[child][0],dp[child][1]);
    }
}

void track(int prev, int cur, bool state){
    if(state){ // state==1, cur 노드가 독립집합에 포함되어야 된다는 뜻, child는 전부 빠져야 된다는 것
        ansvec.push_back(cur);
        for(auto child:edge[cur]){
            if (child==prev) continue;
            track(cur, child, 0);
        }
    }
    else{ //state==0, child 노드의 dp값을 보면서 들어 가는게 최대값을 만들게 하는지 안들어 가는게 최댓값을 만들게 하는지를 봐라.
        for(auto child:edge[cur]){
            if(child==prev) continue;
            if(dp[child][1]>=dp[child][0])
                track(cur, child, 1);
            else
                track(cur, child, 0);
        }
    }
}
int main(void){
    cin>>n;
    edge.resize(n+1);
    for(int i=1; i<=n; i++) cin>>cost[i];
    for(int i=1; i<n; i++){
        int a,b;
        cin>>a>>b;
        edge[a].push_back(b);
        edge[b].push_back(a);
    }
    dfs(1);
    int ans0 = dp[1][0];
    int ans1 = dp[1][1];
    if(ans0>ans1){
        track(-1, 1, 0);
    }
    else{
        track(-1, 1, 1);
    }
    sort(ansvec.begin(),ansvec.end());
    cout<<max(ans0,ans1)<<"\n";
    for(int n: ansvec) cout<<n<<" ";
}