백준 2213번 트리의 독립집합 c++ 풀이

문제

그래프 G(V, E)에서 정점의 부분 집합 S에 속한 모든 정점쌍이 서로 인접하지 않으면 (정점쌍을 잇는 간선이 없으면) S를 독립 집합(independent set)이라고 한다. 독립 집합의 크기는 정점에 가중치가 주어져 있지 않을 경우는 독립 집합에 속한 정점의 수를 말하고, 정점에 가중치가 주어져 있으면 독립 집합에 속한 정점의 가중치의 합으로 정의한다. 독립 집합이 공집합일 때 그 크기는 0이라고 하자. 크기가 최대인 독립 집합을 최대 독립 집합이라고 한다.

문제는 일반적인 그래프가 아니라 트리(연결되어 있고 사이클이 없는 그래프)와 각 정점의 가중치가 양의 정수로 주어져 있을 때, 최대 독립 집합을 구하는 것이다.

입력

첫째 줄에 트리의 정점의 수 n이 주어진다. n은 10,000이하인 양의 정수이다. 1부터 n사이의 정수가 트리의 정점이라고 가정한다. 둘째 줄에는 n개의 정수 w1, w2, ..., wn이 주어지는데, wi는 정점 i의 가중치이다(1 ≤ i ≤ n). 셋째 줄부터 마지막 줄까지는 간선의 리스트가 주어지는데, 한 줄에 하나의 간선을 나타낸다. 간선은 정점의 쌍으로 주어진다. 입력되는 정수들 사이에는 빈 칸이 하나 있다. 가중치들의 값은 10,000을 넘지 않는 자연수이다.

출력

첫째 줄에 최대 독립집합의 크기를 출력한다. 둘째 줄에는 최대 독립집합에 속하는 정점을 오름차순으로 출력한다. 최대 독립 집합이 하나 이상일 경우에는 하나만 출력하면 된다.

예제 입력 1 복사

7
10 30 40 10 20 20 70
1 2
2 3
4 3
4 5
6 2
6 7

예제 출력 1 복사

140
1 3 5 7

 

 

트리와 DP를 활용한 문제이다.

정점을 선택했을 때와 선택하지 않았을 때를 1과 0으로 표현하여서 dp[now][1] dp[now][0]으로 메모제이션을 해 준다.

dfs를 통해서 모든 정점을 방문하면서 정점을 선택했을 때와 선택하지 않았을 때를 메모제이션을 해서 탑다운 방식으로 dp를 채워준 후 가장 큰 값인 dp[1][0]과 dp[1][1]의 값 중 더 큰 값에 따라서 시작점을 선택한 트래킹, 시작점을 선택하지 않은 트래킹으로 나누어서 현재 노드에서 최대의 가중치를 가지는 DP를 따라서 정점을 하나씩 저장해 준다. 그리고 출력하는 문제이다.

 

 

- c++ 풀이 (풀이 참고 : https://cocoon1787.tistory.com/482)

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

int n, a, b, x, ans1, ans2;
int V[10001]; // weight
int dp[10001][2]; //
bool visit[10001];
vector<int> graph[10001];
vector<int> ans;

void DFS(int now)
{
    visit[now] = true;
    dp[now][1] = V[now];

    for (int child : graph[now])
    {
        if (!visit[child])
        {
            DFS(child);

            // 현재 노드를 포함하지 않는다면
            // 자식노드를 포함하는것과 포함하지 않는것 둘 중 큰 것을 채택
            dp[now][0] += max(dp[child][0], dp[child][1]);

            // 현재 노드를 포함한다면 자식노드는 포함 X
            dp[now][1] += dp[child][0];
        }
    }
}

void tracking(int prev, int now, int state) // 이전노드, 현재노드, 포함유무
{
    if (state == 1) // 현재 노드를 포함한다면
    {
        ans.push_back(now);

        for (int child : graph[now])
        {
            // 이전 노드라면 패스
            if (child == prev) continue;

            // 현재 노드를 포함했으므로 자식노드는 포함 X
            tracking(now, child, 0);
        }
    }
    else
    {
        for (int child : graph[now])
        {
            // 이전 노드라면 패스
            if (child == prev) continue;

            if (dp[child][0] > dp[child][1])
                // 다음 노드 포함 X
                tracking(now, child, 0);

            else
                // 다음 노드 포함 O
                tracking(now, child, 1);
        }
    }
}

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

    cin >> n;

    for (int i = 1; i <= n; i++)
        cin >> V[i];

    for (int i = 1; i <= n - 1; i++)
    {
        cin >> a >> b;
        graph[a].push_back(b);
        graph[b].push_back(a);
    }

    DFS(1);

    ans1 = dp[1][0];
    ans2 = dp[1][1];

    if (ans1 > ans2) tracking(-1, 1, 0);
    else tracking(-1, 1, 1);

    cout << max(ans1, ans2) << '\n';

    sort(ans.begin(), ans.end());

    for (int x : ans)
    {
        cout << x << " ";
    }
}