[ 백준 BOJ ] 2533번 - 사회망 서비스(SNS) (C++)

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

 

 

생각흐름

• 한 노드에 대해 밑에 자식 중에 얼리어답터가 없으면 얼리어답터로 만들어줘야 한다.
• 구현과정은 https://rosoa0475.tistory.com/417 문제와 동일하다.

 

 

#include <iostream>
#include <vector>
#include <map>
#include <queue>

#define endl '\n'

using namespace std;

int N;
vector<int> edge[1000001];
bool checked[1000001];
int answer;

bool recur(int parentNode, int nowNode){
    if(parentNode != -1 && edge[nowNode].size()==1){
        return false;
    }
    
    for(int i = 0; i<edge[nowNode].size(); i++){
        if(parentNode == edge[nowNode][i]) continue;
        
        if(!recur(nowNode, edge[nowNode][i])&&!checked[nowNode]){
            answer++;
            checked[nowNode]=true;
        }
    }
    
    return checked[nowNode];
}

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    
    cin>>N;
    
    for(int i = 1; i<N; i++){
        int a,b;
        cin>>a>>b;
        edge[a].push_back(b);
        edge[b].push_back(a);
    }
    
    recur(-1, 1);
    
    cout<<answer<<endl;
    
    return 0;
}