[BOJ 2213 // C++] 트리의 독립집합

※ 글쓴이는 취미로 코딩을 익혀보는 사람이라 정확하지 않은 내용을 담고 있을 수 있다 ※

 

이번에 볼 문제는 백준 2213번 문제인 트리의 독립집합이다.
문제는 아래 링크를 확인하자.

www.acmicpc.net/problem/2213

2213번: 트리의 독립집합

이 문제에서는, 노드에 가중치가 주어진 트리에서 서로 인접한 노드가 포함되지 않으면서 선택된 노드의 가중치의 합이 최대가 되게끔 노드를 선택하고, 그 노드를 출력하는 문제해야 한다.

 

방법은 여러 가지가 있겠지만, 글쓴이는 각 자식노드에 대하여 그 노드를 포함한 경우의 최댓값과 그때의 선택된 노드, 그 노드를 포함하지 않은 경우의 최댓값과 그때의 선택된 노드를 구하는 부분문제 재귀적으로 풀고, 이를 종합하여 문제를 해결하였다.

 

특히, 선택된 노드들을 벡터에 담아서 return값에 넣어서 코드를 만들었는데, 다음번에는 코드를 조금 더 깔끔하게 만들 수 있도록 신경써봐야 할 것 같다.

 

아래는 제출한 소스코드이다.

#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
using std::cin; using std::cout;
using std::vector;
using std::pair;
using std::sort;
using std::max;

vector<int> G[10001];
int weight[10001];

pair<pair<int, int>,pair<vector<int>, vector<int>>> dfs(int root, int parent){
    vector<int>::iterator iter = G[root].begin();
    int included = weight[root];
    int excluded = 0;
    vector<int> instack = { root };
    vector<int> exstack;
    while (iter != G[root].end()) {
        if (*iter == parent) {
            iter++; continue;
        }
        pair<pair<int,int>,pair<vector<int>, vector<int>>> temp = dfs(*iter, root);
        included += temp.first.second;
        vector<int>::iterator iteriter = temp.second.second.begin();
        while (iteriter != temp.second.second.end()) {
            instack.push_back(*iteriter);
            iteriter++;
        }
        if (temp.first.first > temp.first.second) {
            excluded += temp.first.first;
            iteriter = temp.second.first.begin();
            while (iteriter != temp.second.first.end()) {
                exstack.push_back(*iteriter);
                iteriter++;
            }
        }
        else {
            excluded += temp.first.second;
            iteriter = temp.second.second.begin();
            while (iteriter != temp.second.second.end()) {
                exstack.push_back(*iteriter);
                iteriter++;
            }
        }
        iter++;
    }
    return {{included, excluded}, {instack, exstack}};
}

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

    int N; cin >> N;
    for (int i = 1;i <= N;i++) {
        int temp; cin >> temp; weight[i] = temp;
    }
    for (int i = 1;i < N;i++) {
        int x, y; cin >> x >> y;
        G[x].push_back(y);
        G[y].push_back(x);
    }
    pair<pair<int, int>, pair<vector<int>, vector<int>>> ans = dfs(1, 0);

    if (ans.first.first > ans.first.second) {
        cout << ans.first.first << '\n';
        sort(ans.second.first.begin(), ans.second.first.end());
        for (vector<int>::iterator iter = ans.second.first.begin();iter != ans.second.first.end();iter++) cout << *iter << ' ';
    }
    else {
        cout << ans.first.second << '\n';
        sort(ans.second.second.begin(), ans.second.second.end());
        for (vector<int>::iterator iter = ans.second.second.begin();iter != ans.second.second.end();iter++) cout << *iter << ' ';
    }
    return 0;
}