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

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

2213번: 트리의 독립집합

서로 이웃하지 않는 정점들의 가중치 합의 최대를 구하고 그것을 역추적하는 문제이다.

 

가중치 합의 최대만을 구하라 하면 다른 골드 3 tree dp 문제와 다름이 없으므로

그것을 역추적하는 방법에 대해서만 대략적인 설명을 할 생각이다.

 

처음 tree dp를 진행할 때, 다음 노드를 선택한 경우와 선택하지 않은 경우 중 최대를 골라 저장하는 부분이 있다.

그때 역추적을 위한 tranking 배열에 표시를 해놓으면서 tree dp를 진행한다.

 

다음 노드를 선택할 때가 최대일 경우 tracking 배열에 다음 노드를 사용했다는 표시를 해준다.

반대로 선택하지 않을 경우 tracking 배열에 다음 노드를 사용하지 않았다는 표시를 해준다.

(사용 여부 표시를 1,0으로 하고, tracking 배열의 초기값이 0일 때 선택하지 않을 경우를 표시할 필요는 없다)

 

tree dp가 끝난 뒤에는 다시 tree를 재귀적으로 탐색하며, ans vector에 정답인 정점들을 넣어준다.

재귀 함수의 파라미터로는 현재의 정점 번호와, 그 정점을 선택한 여부를 사용한다.

 

파라미터로 받은 정점 번호를 cur, 선택여부를 chk라 하자.

 

만약 chk가 1이라면 cur 정점을 선택했다는 의미이므로

cur정점과 인접한 정점들은 선택하면 안 된다.

따라서 cur정점과 인접한 정점을 next라 할 때,

next와 0을 파라미터로 넘겨준다.

 

만약 chk가 0이라면 cur 정점을 선택하지 않았다는 의미이므로

cur정점과 인접한 정점들은 선택 여부를 기록해 놓은 tracking 배열에 따라 선택한다.

따라서 cur정점과 인접한 정점을 next라 할 때,

next와 tracking[next]를 파라미터로 넘겨준다.

 

탐색해서 얻은 ans배열을 오름차순으로 출력하라 하였으니 정렬하여 출력한다.

 

※주의사항

만약 ans배열에 1이 포함되어야 할 때,

dfs를 1부터 시작하게 되면 tracking 배열에 1은 표시가 되지 않는다.

따라서 dp값을 비교하여 표시를 해야 할 때 따로 표시를 해주어야 한다.

 

+) 왜 재귀적으로 tracking을 하는 것인가.

tracking 배열은 tree dp를 진행시키며 표시를 해온 것이므로,

정답이 아닌 정점이 표시가 되어있을 수 있다.

따라서 문제에서 제시한 정점 선택 규칙을 따라가며 정답을 구한다.

다음 예시에서 ans배열과, tracking배열을 출력해 보면 쉽게 알 수 있을 것이다.

(인접한 정점이 최대인 것으로 업데이트 될 때 이런 현상이 일어난다)

7
500 100 100 1 1 1 1
1 2
1 3
2 4
2 5
3 6
3 7

정답 코드

#include<bits/stdc++.h>
using namespace std;
int n;
vector<int> ans;
int dp[10100][2];
int weight[10100];
int visited[10100];
bool tracking[10100];
vector<int> tree[10100];

void dfs(int cur){
    if(visited[cur])
        return;
    visited[cur] = 1;
    dp[cur][0] = 0;
    dp[cur][1] = weight[cur];
    for(auto next : tree[cur]){
        if(visited[next])
            continue;
        dfs(next);
        if(dp[next][1] > dp[next][0]){
            dp[cur][0] += dp[next][1];
            tracking[next] = 1;
        }
        else{
            dp[cur][0] += dp[next][0];
            tracking[next] = 0;
        }
        dp[cur][1] += dp[next][0];
    }
}

void track(int cur, bool chk){
    if(visited[cur])
        return;
    visited[cur] = 1;
    if(chk){
        ans.push_back(cur);
        for(auto next : tree[cur]){
            if(visited[next])
                continue;
            track(next,0);
        }
    }
    else{
        for(auto next : tree[cur]){
            if(visited[next])
                continue;
            track(next,tracking[next]);
        }
    }
}

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    //input
    cin>>n;
    for(int i=1; i<=n; i++)
        cin>>weight[i];
    for(int i=1; i<n; i++){
        int u,v; cin>>u>>v;
        tree[u].push_back(v);
        tree[v].push_back(u);
    }
    //tree dp
    dfs(1);
    //예외 처리
    if(dp[1][1]>dp[1][0]) tracking[1] = 1;
    else tracking[1] = 0;
    //역추적
    memset(visited,0,sizeof(visited));
    track(1,tracking[1]);
    //output
    cout << max(dp[1][1],dp[1][0]) << '\n';
    sort(ans.begin(),ans.end());
    for(auto i : ans)
        cout << i << ' ';
    return 0;
}