BOJ 2213 트리의 독립집합

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

2213번: 트리의 독립집합

목차

• 독립 집합의 크기
• 최대 독립 집합의 원소들 찾기

 독립 집합의 크기

독립 집합의 정의는 다음과 같다.

그래프 G(V, E)에서 정점의 부분 집합 S에 속한 모든 정점쌍이 서로 인접하지 않으면 (정점쌍을 잇는 에지가 없으면) S를 독립 집합(independent set)이라고 한다.

또한 독립 집합의 크기는 다음과 같이 정의된다.

가중치가 주어져 있지 않을 경우는 독립 집합에 속한 정점의 수를 말하고, 정점에 가중치가 주어져 있으면 독립 집합에 속한 정점의 가중치의 합으로 정의한다.

이 중 가중치의 합이 가장 큰 독립 집합을 최대 독립 집합이라 한다.

 

이 문제에서는 일반적인 그래프에서의 독립 집합이 아닌, 트리에서의 최대 독립 집합을 구하는 문제이다.

 

예제의 그래프는 다음과 같다.

초기 상태

각각의 정점은 자신을 (포함하는 경우의 가중치 : w, 포함하지 않는 경우의 가중치 : 0)으로 초기화 돼있다.

 

독립 집합을 구하기 위해 각 정점별로 자신을 포함 하는  독립 집합, 포함하지 않는 독립 집합의 가중치의 합을 각각 저장했다. leaf 노드부터 탐색을 시작한(root) 노드까지 각각의 경우 가중치의 합을 저장해야 하므로 깊이우선탐색을 이용한 백트래킹을 이용, leaf 노드부터 root까지 각각 경우(자신을 포함, 포함x)의 가중치의 합을 저장했다.

 

정의에 따르면 독립 집합은 모든 정점 쌍이 서로 인접하지 않은 정점들의 집합이므로,

  1. 자신을 포함하는 경우 -> 인접한 정점 선택 불가

  2. 자신을 포함하지 않는 경우 -> 인접한 정점을 포함하거나 하지 않거나 모두 가능

 

따라서 다음 식을 이용하면 현재 방문하는 정점부터 부트리에 포함되는 정점들을 모두 포함한 최대 독립 집합의 크기를 구할 수 있다.

 

현재 방문하는 정점을 cur, cur에 인접한 정점을 adj라고 하자

 

  1. arr[cur].[cur을 포함 하는 경우] += arr[adj]

 - 자신을 포함하는 경우 -> 인접한 정점 선택 불가

 

  2. arr[cur].[cur을 포함 안하는 경우] += max( arr[adj].(adj 포함) , arr[adj].(adj 포함x) )

 - 자신을 포함하지 않는 경우 -> 인접한 정점을 포함하거나 하지 않거나 모두 가능

 

 

위 식을 실행하면 다음과 같은 가중치를 얻을 수 있다.

실행 후

독립 집합의 크기는 위와 같이 찾을 수 있다.

 

최대 독립 집합의 원소 찾기

독립 집합의 크기를 찾은 후에는 최대 독립 집합의 원소를 찾아야 한다.

 

최대 독립 집합의 원소를 찾기 위해서는 각 정점별로 어떤 경우(포함, 포함x)를 택했는지가 필요하다.

정점별로 자신을 포함 했으면 최대 독립 집합의 원소가 되고, 자신을 포함하지 않았으면 최대 독립 집합의 원소에 포함되지 않기 때문이다.

 

따라서 dfs 탐색을 시작한 정점의 가중치를 최대로 하는 경우(포함, 포함x)부터 시작해 인접한 정점들에 대해 탐색한다.

 

최대 독립 집합의 원소를 찾기 위해서는 각 정점별 가중치를 최대로 하는 경우(포함, 포함x) 의 선택 결과를 기억해야 하는데, 이를 저장하는 배열을 choice[]라 하자.

 

choice 배열에는 각 정점별 가중치를 최대로 하는 경우(포함 = 1, 포함x = 2)를 저장한다.

 

choice 배열에 값을 넣는 코드는 다음과 같다.

// 현재 방문하는 정점 v에 대해
for(int adj:G[v]) { // 인접한 정점을 adj라 하자.
        if(!visited[adj]) {
            P tmp = dfs(G,arr,adj,visited); // 인접한 정점들의 가중치 tmp에 저장됨.
            arr[v].inc += tmp.n_inc;
            arr[v].n_inc += max(tmp.n_inc, tmp.inc);
            // v를 포함하지 않는 최대 독립집합 -> 포함/포함x 경우의 최대 합
            
            if (arr[adj].inc > arr[adj].n_inc) choice[adj] = INC; // 포함
            else choice[adj] = N_INC; // 포함x
            // 각 정점별 어떤 값을(포함/포함x) 취했는지 choice 배열에 저장
            // 현재 방문하는 정점(v)가 아닌 인접한 정점에 대해 choice 값을 업데이트 하는 이유?
        }

현재 방문하는 정점 v 가 아닌 인접한 정점 adj에 대해 choice 값을 설정하는 이유는 현재 계속 업데이트 되는 정점 v와 달리, 인접한 정점들의 가중치 업데이트는 이미 이전 dfs 탐색(3번째 라인)에 의해 끝났기 때문

각 정점별 자신을 포함 하는지, 하지 않는지가 choice 배열에 저장되었으므로, 다시 한 번 dfs 탐색을 통해 자신을 포함하는 원소들을 결과 배열에 추가하면 된다.

 

void chosen(vector<int> G[], bool visited[], int cur, int Choice) {
    // 정점별 choice를 이용해 최대 독립집합을 구하기
    visited[cur] = true;
    if (Choice == INC) {
        ans.push_back(cur); // 자기 자신을 포함하는 경우 결과 배열에 추가
        for (auto next : G[cur]) {
            if(!visited[next]) chosen(G, visited, next, N_INC); // 다음을 포함하지 않는 경우
            // choice[next]로 해도 무관
        }
    } else { // 현재 정점을 포함 하는 경우
        for(auto next : G[cur])
            if(!visited[next]) chosen(G, visited, next, choice[next]);
            // 각 정점의 선택을 따름
    }
}

 

 

전체 코드는 다음과 같다.

#include <cstdio>
#include <vector>
#include <cstring>
#include <algorithm>

using namespace std;
int N;
struct P {int inc, n_inc;};
const int INC = 1, N_INC = 2;
vector<int> ans;
short choice[10003];

P dfs(vector<int> G[], P arr[], int v, bool visited[]) { // 최대 독립집합의 가중치 합 구하기
    visited[v] = true;
    for(int adj:G[v]) { // v를 포함하지 않는 최대 독립 집합 -> 자식 노드들 포함/포함x
        if(!visited[adj]) {
            P tmp = dfs(G,arr,adj,visited);
            arr[v].inc += tmp.n_inc;
            arr[v].n_inc += max(tmp.n_inc, tmp.inc);
            // v를 포함하지 않는 최대 독립집합 -> 포함/포함x 경우의 최대 합
            if (arr[adj].inc > arr[adj].n_inc) choice[adj] = INC;
            else choice[adj] = N_INC;
            // 각 정점별 어떤 값을(포함/포함x) 취했는지 choice 배열에 저장
        }
    }
    return arr[v];
}

void chosen(vector<int> G[], bool visited[], int cur, int Choice) {
    // 정점별 choice를 이용해 최대 독립집합을 구하기
    visited[cur] = true;
    if (Choice == INC) {
        ans.push_back(cur);
        for (auto next : G[cur]) {
            if(!visited[next]) chosen(G, visited, next, N_INC); // 다음을 포함하지 않는 경우
            // choice[next]로 해도 무관
        }
    } else { // 현재 정점을 포함 하는 경우
        for(auto next : G[cur])
            if(!visited[next]) chosen(G, visited, next, choice[next]);
            // 각 정점의 선택을 따름
    }
}

int main() {
    scanf("%d",&N);
    P arr[N+1];
    for(int i=1;i<=N;++i)
        arr[i] = {1,0};
    for(int i=1;i<=N;++i)
        scanf("%d",&arr[i].inc);
    vector<int> G[N+1];
    for(int i=0;i<N-1;++i) {
        int u, v;
        scanf("%d%d",&u,&v);
        G[u].push_back(v);
        G[v].push_back(u);
    }

    bool visited[N+1];
    memset(visited,0, sizeof(visited));

    dfs(G,arr,1,visited); // 최대 독립 집합 구하기

    memset(visited,0, sizeof(visited));
    if (arr[1].inc > arr[1].n_inc) // 가중치의 합이 가장 큰 최대 독립 집합
        chosen(G,visited,1,INC);
    else
        chosen(G,visited,1,N_INC);
    printf("%d\n",max(arr[1].inc, arr[1].n_inc));
    sort(ans.begin(),ans.end());
    for(auto e:ans)
        printf("%d ",e);
}