[알고리즘 문제] 2213번 트리의 독립집합

2213번: 트리의 독립집합

 

 

1. 분석 및 고찰

전에 포스팅했던 1272문제와 다른 tree dp문제를 경험했던 덕분에 각 노드가 루트가 되고 해당 노드의 상태가 0 혹은 1일때로 나누어 계산하면 된다는 점을 바로 깨달을 수 있었다. 

 

2. 실패

이 문제는 추가적으로 back-tracking 과정을 걷혀야 하는데 이를 dp 업데이트 도중에 갱신하고자 하였으나 $N^2$의 공간 복잡도 문제로 고민하는 데 시간을 많이 소비하였다.

 

3. 성공

back-tracking은 구지 경로를 남길 필요는 없다. dynamic table을 만들고 dfs를 통해 최댓값이 되기 위해 해당 노드가 어떤 선택을 취했는지 이미 dp를 통해 알 수 있다. 따라서 기존에 dynamic table의 정보 중 더 큰 상태를 선택하고 해당 노드를 경로 vector에 넣어 후에 출력하면 된다.

 

4. 코드

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

int N, w[10005], dt[10005][2], c;
vector<int> v[10005], ans;

void track(int n, int bef, int type)
{
    for(auto&i:v[n]){
        if(i == bef) continue;
        if(type) track(i, n, 0);
        else{
            int now = 0;
            if(dt[i][0] < dt[i][1]) now = 1;
            track(i, n, now);
            if(now) ans.push_back(i);
        }
    }
}

void p(int n, int bef, int type)
{
    if(dt[n][type]) return;
    int yes = w[n], no = 0;
    for(auto&i:v[n]){
        if(i == bef) continue;
        p(i, n, 0);
        if(type == 0){
            p(i, n, 1);
            no += max(dt[i][0], dt[i][1]);
        }
        else yes += dt[i][0];
    }
    if(!type) dt[n][0] = no;
    else dt[n][1] = yes;
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
    int x, y;
    cin >> N;
    for(int i=1;i<=N;i++) cin >> w[i];
    for(int i=1;i<N;i++){
        cin>>x>>y;
        v[x].push_back(y); v[y].push_back(x);
    }
    p(1, 0, 0); c=1; p(1, 0, 1);
    cout << max(dt[1][0], dt[1][1]) <<"\n";
    if(dt[1][0] < dt[1][1]){ track(1,0,1); ans.push_back(1);}
    else track(1, 0, 0);
    sort(ans.begin(), ans.end());
    for(auto&i:ans) cout << i << " ";
}

 

5. 소감 및 느낀점

이 전에 비슷한 유형을 여러 번 풀어 보았기에 비교적 쉽게 풀 수 있었다. 만약 해당 문제가 어렵게 느껴진다면 이 전 포스팅을 참고하여 학습하면 도움이 될 것이다. 그리고 이 문제에서 느낀 것은 dp와 back-tracking 을 융합한 유형 중 tree에서의 dp는 신선했고 한 기능을 한 번에 끼어 넣을라고 욕심부리지 말고 쫌 침착하게 생각하면 앞으로 문제 푸는데 더 수월해질 것이라 느꼈다.