[백준]사회망 서비스(SNS)(2533)

문제 링크 : [백준]사회망 서비스(SNS)(2533)

2533번: 사회망 서비스(SNS)

문제 설명

N개의 노드로 이루어진 트리가 주어지고, 각 노드는 얼리어답터이거나 자신과 인접한 모든 노드들이 얼리어답터이어야 합니다.

적당히 얼리어답터를 선정했을 때 위 조건을 만족하도록 만들어야 하는데, 그때 최소로 얼리어답터를 지정할 수 있는 수가 몇명인지 구하세요.

입력

N(노드의 수, 2 <= N <= 1,000,000)

U_i V_i(간선 정보)

8
1 2
1 3
1 4
2 5
2 6
4 7
4 8

 

출력

3

 

카테고리

#DP #트리

 

시간 복잡도 상한

O(NlogN)

 

해결 방법

1. 모든 사람들에 대하여 얼리어답터인 경우와 얼리어답터가 아닌 경우를 대입하보면 구할 수 있습니다.
2. 부모 노드의 얼리어답터 여부에 따라서 두가지 경우로 나누어집니다.
   1. 부모 노드가 얼리어답터인 경우, 자식 노드들은 얼리어답터가 되어도 되고, 얼리어답터가 아니어도 됩니다.
   2. 부모 노드가 얼리어답터가 아닌 경우, 자식 노드는 반드시 얼리어답터가 되어야합니다.(인접한 노드 중 적어도 하나가 얼리어답터가 아니기 때문(부모))
3. 루트를 시작으로, 각 자식 노드들을 루트로 하는 서브트리로 만들어서, 위 두가지 경우에 대하여 최소가 되는 서브트리들의 값들을 취합합니다.다음과 같은 재귀 함수가 정의 될 수 있습니다.

   int r(int p,int s){
   	int value=0;
       w[p]=1;
       for(int i=0;i<v[p].size();i++){
           if(w[v[p][i]])continue;//이미 방문한 노드(부모)라면 무시함
           int temp=r(v[p][i],1);//자식 노드를 루트로 하는 서브트리에 대하여, 자식이 얼리어답터인 경우의 최소 얼리어답터 수를 구함
           if(s==1)temp=min(r(v[p][i],0),temp);//자신이 얼리어답터인 경우에 한하여, 자식 노드를 루트로 하는 서브트리에 대하여, 자식이 얼리어답터가 아닌 경우의 최소 얼리어답터 수를 구함
   		value+=temp;
       }
       w[p]=0;
       return value;
   }

4. 하지만 시간복잡도가 O(2^N)이기 때문에 타임아웃이 납니다.

5. 그러나 호출 관계를 따지다 보면 중복된 경우에 대한 호출이 빈번함을 알 수 있습니다.
6. 또한 K번 노드가 얼리어답터 이거나 얼리어답터가 아닌 경우에 대하여 자신을 포함한 하위 노드들에 대한 최소 얼리어답터 수는 고정이 되어 있습니다.
7. 따라서 함수 호출에 대하여 매번 계산 할 것이 아니라, 메모이제이션을 이용하여 함수 호출 횟수를 줄일 수 있습니다.

시간복잡도

O(N)

코드

#include<cstdio>
#include<vector>
#include<algorithm>
using namespace std;
int n,x,y,i,d[2][1000001],w[1000001];
vector<int> v[1000001];
int r(int p,int s){
    if(d[s][p])return d[s][p];
    w[p]=1;
    for(int i=0;i<v[p].size();i++){
        if(w[v[p][i]])continue;
        d[s][p]+=min(r(v[p][i],1),s?r(v[p][i],0):1000002);
    }
    d[s][p]+=s;
    w[p]=0;
    return d[s][p];
}
int main(){
    scanf("%d",&n);
    for(;i<n-1;i++){
        scanf("%d%d",&x,&y);
        v[x].push_back(y);
        v[y].push_back(x);
    }
    printf("%d",min(r(1,0),r(1,1)));
}