[Baekjoon,2533] 사회망 서비스(SNS)

트리에서 최소한의 얼리 어답터를 배치하는 문제이다. 종만북의 GALLERY문제와 해결 법이 비슷하다. 손으로 풀다 보면 트리의 잎 노드에는 얼리 어답터를 배치하지 않는것이 결과를 최소화 할 수 있다는 것을 알 수 있다. 이때 문제에서 제시한 아래의 문구가 중요하다.

“얼리 아답터가 아닌 사람들은 자신의 모든 친구들이 얼리 아답터일 때만 이 아이디어를 받아들인다.”

이는 종만북 문제와는 다르게 자신의 자식 노드들 중 하나라도 얼리 어답터가 아닌 경우 항상 자신은 얼리 어답터가 되어야 하게 함수를 설정해야 한다. 이를 코드로 구현하면 아래와 같다. $bool$ 변수를 이용하여 자식들이 어떤 상태인지 얻고 있는 것을 눈여겨 보자.

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

const int MAX_V=1000001;

int V;
vector<int> adj[MAX_V];
bool visited[MAX_V];
int counter;

bool isEarlyAdaptor(int here)
{
    visited[here]=true;
    bool ret=false;
    // 자식들을 탐색한다. 
    for(int i=0;i<adj[here].size();++i)
    {
        int there=adj[here][i];
        if(!visited[there])
        {
            // 자식이 얼리 어답터가 아닌 경우 
            if(!isEarlyAdaptor(there))
                ret=true;
        }
    }
    // 자식 중 하나라도 얼리 어답터가 아닌 경우 
    // 본인은 얼리 어답터이다. 
    if(ret)
    {
        ++counter;
        return true;
    }
    // 자식 중 일반 유저가 하나도 없으면 유저를 반환 
    return false;
}

int main()
{
    cin>>V;
    for(int i=0;i<V-1;++i)
    {
        int a,b;
        scanf("%d %d",&a,&b);
        adj[a].push_back(b);
        adj[b].push_back(a);
    }
    memset(visited,false,sizeof(visited));
    counter=0;
    isEarlyAdaptor(1);
    cout<<counter<<endl;
    return 0;
}