[C++] 2213번 트리의 독립집합 - DP, 트리, 트리에서 DP

1. 문제

• 그래프에서 정점의 부분 집합 S에 속한 모든 정점쌍이 인접하지 않으면 S를 독립 집합이라고 한다. 트리와 각 정점의 가중치가 양의 정수로 주어졌을 때, 최대 독립 집합을 구하시오.

<입력>

• - 1 -   트리의 정점수 \(n(1 \leq n \leq 10,000)\)
• - 2 -   n개의 정수, 정점 i의 가중치 \(w_{i}(1 \leq w{i} \leq 10,000, 1 \leq i \leq n)\)
• - 3 ~ 마지막 줄 -   정점의 쌍으로 간선이 주어짐

<출력>

• - 1 -   최대 독립집합의 크기
• - 2 -   최대 독립집합에 속하는 정점을 오름차순으로 출력
  • 최대 독립집합이 여러 개인 경우 하나만 출력하면 된다.

2. 재정의

• 트리에서 최대 독립 집합 구하기

3. 해결 방법

• dp[no][0] += max(dp[next][0], dp[next][1])
• dp[no][1] += dp[next][0]
• 이를 통해 back propagation(역추적)하기

4. 실수한 점, 개선할 점

• back propagation 할 때 항상 다음 정점을 추가하기 때문에 1번 정점도 고려해서 추가해줘야 한다.

 

<코드>

#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

const int MAX_N = 10001;

// <문제>
// 트리의 정점수 N
int N;
// 정점의 가중치 w[]
int w[MAX_N];
// 무방향 트리 adj
vector<int> adj[MAX_N];

// dp
int dp[MAX_N][2];
int vi[MAX_N];
// back propagation
vector<int> MaxIndependentSet;

void input() {
    cin >> N;
    for(int i=1; i<=N; i++)
        cin >> w[i];
    for(int i=0; i<N-1; i++) {
        int a, b;
        cin >> a >> b;
        adj[a].push_back(b);
        adj[b].push_back(a);
    }
}

// DFS로 탐색하면서 dp 채우기
void DFS(int no) {
    vi[no] = 1;
    for(auto next : adj[no]) {
        // 아직 지나가지 않은 정점인 경우
        if(!vi[next]) {
            DFS(next);
            // 최대 독립 집합에 no가 포함되지 않으면 그 다음 거는 자유
            // no가 포함되면 다음 거는 최대 독립 집합에 포함되어 있으면 안됨
            dp[no][0] += max(dp[next][0], dp[next][1]);
            dp[no][1] += dp[next][0];
        }
    }
    // 현 정점 가중치 더해주기
    dp[no][1] += w[no];
}

// DP 역추적하면서 최대 독립 집합 구해주기
void BackPropagation(int no, int flag) {
    vi[no] = 1;
    for(auto next : adj[no]) {
        if(!vi[next]) {
            // no가 최대 독립 집합에 포함되어 있는 경우
            if(flag)
                BackPropagation(next, 0);
            // no가 최대 독립 집합에 포함되어 있지 않은 경우
            else {
                if(dp[next][0] >= dp[next][1])
                    BackPropagation(next, 0);
                else {
                    MaxIndependentSet.push_back(next);
                    BackPropagation(next, 1);
                }
            }
        }
    }
}

void print() {
    cout << max(dp[1][0], dp[1][1]) << '\n';
    // 최대 독립 집합 오름차순 정렬하기
    sort(MaxIndependentSet.begin(), MaxIndependentSet.end());
    for(auto x : MaxIndependentSet)
        cout << x << ' ';
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    
    input();
    
    DFS(1);
    
    // DP 역추적
    // vi 초기화 하기
    fill(vi, vi+MAX_N, 0);
    if(dp[1][0] > dp[1][1])
        BackPropagation(1, 0);
    else {
        MaxIndependentSet.push_back(1);
        BackPropagation(1, 1);
    }
    
    print();
    
    return 0;
}

 

<문제 바로가기>

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

2213번: 트리의 독립집합

 

※현재 고등학교 등교 중인 학생입니다. 이제 알고리즘을 본격적으로 공부하기 시작해서 아직 초보입니다. 혹시 제가 잘못 알고 있는 점이나 더 좋은 풀이 방법이 있어 댓글에 남겨주시면 감사히 하나하나 열심히 읽어보겠습니다. 좋아요, 단순한 댓글 한마디라도 저에겐 큰 힘이 됩니다! 감사합니다.