[BOJ알고리즘, C++]#2213_트리의 독립집합, 트리 DP

 

#1. 문제

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

 

---

 

#2. 풀이

 

1. 트리

https://webddevys.tistory.com/287

[자료구조]#5_트리

트리는 그래프의 한 종류로, 1:N 관계의 계층 구조를 갖는 비 선형 자료구조입니다. 트리는 노드와 노드 간 연결 관계를 표현하는 간선으로 이루어져 있습니다. 트리 자료구조의 노드 개수가 N개라면, 간선의 개수는 N-1개로, 순환 구조를 갖지 않습니다.

 

2. DP

https://webddevys.tistory.com/311

[알고리즘]#5_동적 계획법

동적 계획법은 최적화 기법 중 하나로 입력 크기에 따라 중복되는 하위 문제들을 재귀적으로 해결하고, 기억함으로써 중복 계산을 방지합니다. 일반적으로, DP는 하위 문제의 결과 값을 저장할 배열(Memoization)과 DFS를 활용합니다.

 

3. 트리 + DP

일반적으로, DP는 특히 트리 자료구조 관련 문제를 해결할 때 주로 사용됩니다. 재귀 DFS를 활용하는 DP를 설계하는 방법은 크게 두 가지로 Top-Down 방식과 Bottom-Up 방식이 있습니다. 대부분의 경우, Bottom-Up 방식으로 루트 노드를 시작 정점으로 DFS를 수행하며 하위 노드에 대한 결과 값을 Memoization 하고, 단말 노드에 도착하면 다시 Memoization을 활용해 상위 노드들의 결과 값을 도출합니다. 따라서, 최종 결과 값은 루트 노드에 안착하게 되는 방식입니다.

 

4. Bottom-Up 트리 DP 유형, DFS 작성 방법을 기억해 두자!

1. 먼저, 주어진 입력 정보를 통해 트리를 구성합니다.
2. 루트 노드를 시작 정점으로 DFS를 수행하며 Bottom-Up 트리 DP를 수행합니다.
3. 각 정점에 대하여 두 가지 경우에 대한 결과 값을 저장하고, 이를 통해 상위 문제들에 대한 결과 값을 도출합니다.

 

---

 

#3. 코드

/*
    @문제 : 트리 자료구조에서 최대 독립 집합 찾기
    @설명
            1. 트리 + dfs + dp 삼위일체
            2. 모든 노드에 대하여 두 가지 경우(독립 집합에 포함된 경우, 독립 집합에 포함되지 않을 경우) 계산
            3. dfs 구현이 조금 복잡할 수 있어서, dfs 구조를 외워두는 것도 괜찮아 보임
               각 정점에 대하여 한 가지 경우만 생각하면 단순한데, 두 가지 경우가 되면 조금 복잡해진다.
*/

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

#define MAX 10001

vector<int> tree[MAX]; 
int n, weights[MAX], dp[MAX][2];
vector<bool> visited;
vector<int> answer;

int dfs(int cur)
{
    visited[cur] = true;
    dp[cur][0] = 0;
    dp[cur][1] = weights[cur];

    for(const auto neighbor : tree[cur])
    {
        if(visited[neighbor]) continue;

        dfs(neighbor);

        dp[cur][0] += max(dp[neighbor][0], dp[neighbor][1]);
        dp[cur][1] += dp[neighbor][0];
    }
}

void trace(int node, int included) {
    visited[node] = true;
    if (included) {
        answer.push_back(node);
        for (auto next : tree[node]) {
            if (!visited[next]) trace(next, 0);
        }
    } else {
        for (auto next : tree[node]) {
            if (!visited[next]) {
                if (dp[next][0] < dp[next][1]) trace(next, 1);
                else trace(next, 0);
            }
        }
    }
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    cin >> n;

    visited.resize(n+1, false);

    for(int i=1; i<=n; ++i)
    {
        cin >> weights[i];
    }

    for(int i=0; i<n-1; ++i)
    {
        int u, v;
        cin >> u >> v;

        tree[u].push_back(v);
        tree[v].push_back(u);
    }

    // #1. dfs 수행
    dfs(1);

    // #2. 독립 집합에 포함된 노드 찾기
    fill_n(visited, n+1, false);
    if (dp[1][0] > dp[1][1]) trace(1, 0);
    else trace(1, 1);
    // #3. 정렬 및 출력
    sort(answer.begin(), answer.end());
    cout << max(dp[1][0], dp[1][1]) << "\n";
    for (int i = 0; i < answer.size(); ++i) cout << answer[i] << " ";
    cout << "\n";

    return 0;
}

 

---