[백준 2213] 트리의 독립집합 C++

2213번: 트리의 독립집합

트리 DP

---

1. 문제 해결 아이디어

 

[백준 1949] 우수 마을 C++

 

위 문제와 표현하는 말만 다르지 결국 똑같이 서로 인접하지 않는 정점들의 가중치의 최댓값을 찾는 문제이다.

 

하지만 이번 문제는 어떤 정점들이 가중치의 최댓값을 만들어내는지도 알아내야 한다.

 

 

 

예제 입력의 트리를 그려보았다. 아이패드 처음 사서 글씨가 날아다닌다.

왼쪽 그림의 표는 트리dp의 테이블이다.

 

최댓값을 구하는 과정은 <우수마을> 포스팅에 나름 상세히 적혀있으니 최댓값을 이루는 구성요소를 어떻게 구했는지 알아보자

 

왼쪽의 테이블을 보면 하나의 행 마다 현재 노드를 선택한 경우와 선택하지 않은 경우의 최댓값이 나눠져 있다.

 

그런데 최댓값을 이루는 구성요소는 선택된 노드이므로,

자신이 선택되었을 때의 최댓값이 선택되지 않았을때의 최댓값보다 크다면 해당 노드는 최댓값을 이루는 구성요소가 된다.

 

따라서 dfs를 통해서 트리의 모든 노드를 탐색하며 구성요소를 구해주면 된다. 이때 트리는 양방향으로 입력받았으므로 자신의 부모노드를 다시 탐색하지 않도록 주의한다.

 

---

2. 코드

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
#include <cstring>
#define fasti ios_base::sync_with_stdio(false); cin.tie(0);
#define fastio ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
#define INF 1e9+7
#define pii pair<int, int>
 
typedef long long ll;
// typedef pair<int, int> pii;
 
using namespace std;
 
int cost[10001];
int dp[10001][2];
int N;
bool visited[10001];
vector<int> Tree[10001];
vector<int> Path;
 
void input(){
    cin >> N;
    for(int i = 1; i <= N; i++){
        cin >> cost[i];
    }
    
    int a, b;
    for(int i = 1; i < N; i++){
        cin >> a >> b;
        Tree[a].push_back(b);
        Tree[b].push_back(a);
    }
}
 
void dfs(int now){
    // now가 독립집합에 포함될 때
    // 포함되지 않을 때
    dp[now][0] = 0;
    dp[now][1] = cost[now];
    
    visited[now] = true;
    
    for(int i = 0; i < Tree[now].size(); i++){
        int next = Tree[now][i];
        if(visited[next]) continue;
        
        dfs(next);
        dp[now][0] += max(dp[next][0], dp[next][1]);
        dp[now][1] += dp[next][0];
    }
}
 
void tracing(int now, int prev){
    if(dp[now][1] > dp[now][0] && !visited[prev]){
        Path.push_back(now);
        visited[now] = true;
    }
    
    for(int i = 0; i < Tree[now].size(); i++){
        int next = Tree[now][i];
        if(next == prev) continue;
        tracing(next, now);
    }
}
 
void solve(){
    dfs(1);
    memset(visited, 0, sizeof(visited));
    tracing(1, 0);
    
    sort(Path.begin(), Path.end());
    
    cout << max(dp[1][0], dp[1][1]) << "\n";
    for (auto &w : Path){
        cout << w << " ";
    }
}
 
int main(){
    fastio
    input();
    solve();
    
    return 0;
}​