[Baekjoon,2213] 독립집합

트리의 루트에서 부터 DFS로 탐색하며 현재 정점을 선택하느냐 안 하느냐를 결정하여 최대 독립 집합을 구하는 문제이며 정점의 가중치가 있으니 정점의 개수가 아닌 정점의 가중치가 최대가 되는 독립 집합을 찾아야 한다. 독립 집합에 대한 자세한 설명은 이곳에서 볼 수 있다.

문제에서 현재 정점을 선택한 경우 현재 정점의 가중치를 더하고 독립 집합이어야 하니 다음 정점을 선택하면 안된다. 현재 정점을 선택하지 않은 경우는 다음 정점을 선택하거나 하지 않거나 두 가지 중 큰 방향을 선택하면 된다. 즉, 현재 정점을 선택 했느냐 안 했느냐에 따라 아래의 두 가지로 나뉘는 것이다.

1. 현재 정점을 선택했을 때 -> 현재 가중치를 더하고 다음 정점을 선택하지 않음
2. 현재 정점을 선택 안 했을 때 -> 다음 정점을 선택한다 $or$ 선택 안한다.

경로 탐색

경로를 찾는 것은 다음과 같이 진행하였다. 현재 정점이 선택된 경우 답을 저장하는 배열 $choice$에 저장하고 다음 정점의 선택 여부를 찾는다. 현재 정점을 선택하지 않았으며 다음 정점을 선택하는 것이 선택하지 않는 것 보다 크다면 다음 정점을 선택한다. 현재 정점을 선택했다면 당연히 다음 정점을 선택하지 않는다.

구현

이에 대한 모든 구현을 아래에서 볼 수 있다. 트리 형성 시 한 쪽 방향으로만 간선을 형성하여 이미 방문한 여부를 따로 체크하지 않는 것을 볼 수 있다. (이러면 트리가 연결되지 않을 수 있다..) $0$번 정점에서부터 $0$번을 선택 하느냐 안 하느냐로 나누어 탐색하였으며 이를 $cache$에 저장하는 것을 볼 수 있다.

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

enum{NOT,SELECT};

const int MAX_V=10001;

int V;
int weight[MAX_V],cache[MAX_V][2];
vector<int> adj[MAX_V];
vector<int> choiced;

// 현재 정점을 선택한 경우 select=1 
int dfs(int here, int selected, int prev)
{
    int& ret=cache[here][selected];
    if(ret!=-1)
        return ret;
    
    ret=selected ? weight[here] : 0;
    for(int i=0;i<adj[here].size();++i)
    {
        int there=adj[here][i];
        if(there!=prev)
        {
            int selectHere=dfs(there,NOT,here);
            int selectThere=0;
            if(!selected)
                selectThere=dfs(there,SELECT,here);
            ret+=max(selectHere,selectThere);
        }
    }
    return ret;
}

void reconstruct(int here, int selected, int prev)
{
    if(selected)
        choiced.push_back(here);
    for(int i=0;i<adj[here].size();++i)
    {
        int there=adj[here][i];
        if(there!=prev)
        {
            if(!selected && cache[there][SELECT]>cache[there][NOT])
                reconstruct(there,SELECT,here);
            else
                reconstruct(there,NOT,here);
        }
    }
}

int main()
{
    cin>>V;
    for(int i=0;i<V;++i)
        cin>>weight[i];
    for(int i=0;i<V-1;++i)
    {
        int a,b;
        scanf("%d %d",&a,&b);
        --a;--b;
        adj[a].push_back(b);
        adj[b].push_back(a);
    }
    memset(cache,-1,sizeof(cache));

    int select=dfs(0,SELECT,-1);
    int notSelect=dfs(0,NOT,-1);
    int ret=max(select,notSelect);

    cout<<ret<<endl;
    
    (select>notSelect) ? reconstruct(0,SELECT,-1) : reconstruct(0,NOT,-1);
    
    sort(choiced.begin(),choiced.end());
    for(int i=0;i<choiced.size();++i)
        cout<<choiced[i]+1<<' ';
    return 0;
}

---

회고

떠오른 생각을 코드로 작성하는 것은 어렵고 DP도 어렵다.