BOJ 2213 트리의 독립집합

사용한 알고리즘

DFS, DP, 탐색

알고리즘 설명

독립집합중 가중치의 합이 최대가 되는 독립집합을 찾는 문제이다.
DP를 정의한다. DP(i번째 집합, 포함여부)
위 DP에서 포함여부에 따라 다음 연결되는 요소가 선택 가능 여부가 달라진다.
이 뜻은, 인접한 집합이 포함되어 있는 경우 불포함 조건을 말한다.
최대 값을 DP에서 찾은 뒤에, 다시 DP의 저장된 값을 이용하여 포함될 집합을 찾는다.
찾는 방법은 간단하다. 집합을 포함했을 경우, 안했을 경우 다음 DP와 이어질 수 있는지 판단한다.
찾은 뒤에 출력한다.

풀이

// baekjoon 2213 yechan
#include <cstdio>
#include <algorithm>
#include <vector>
using namespace std;
#define MAX_N 10001

int N;
int weight[MAX_N], dp[MAX_N][2];
int visited[MAX_N];
vector<int> adj[MAX_N];
vector<int> st;

// state:0 (X), 1 (include)
int dfs(int root, int state) {
    if (dp[root][state]) return dp[root][state];

    visited[root]=1;
    int ret = (state) ? weight[root] : 0;
    for (int i=0; i<adj[root].size(); i++) {
        int next = adj[root][i], tmp = 0;
        if (!visited[next]) {
            tmp = dfs(next, 0);
            if (!state) tmp = max(tmp, dfs(next, 1));
        }
        ret += tmp;
    }
    visited[root]=0;

    dp[root][state] = ret;
    return dp[root][state];
}

void backtracking(int root, int state) {
    if (!dp[root][state]) return;

    visited[root]=1;
    if (state) st.push_back(root);

    for (int i=0; i<adj[root].size(); i++) {
        int next = adj[root][i], tmp = 0;
        if (!visited[next]) {
            if (state) backtracking(next, 0);
            else backtracking(next, (dp[next][0] > dp[next][1]) ? 0 : 1);
        }
    }
    visited[root]=0;
}

int main() {
    scanf("%d", &N);
    for (int i=1; i<=N; i++)
        scanf("%d", &weight[i]);

    for (int i=1; i<N; i++) {
        int u, v; scanf("%d %d", &u, &v);
        adj[u].push_back(v);
        adj[v].push_back(u);
    }
    int ret = max(dfs(1,0), dfs(1,1));
    printf("%d\n", max(dfs(1,0), dfs(1,1)));
    int state = (dp[1][0] > dp[1][1]) ? 0 : 1;
    backtracking(1, state);
    sort(st.begin(), st.end());
    for (int i=0; i<st.size(); i++) {
        printf("%d ", st[i]);
    }
    return 0;
}