[BOJ] 2533 사회망 서비스(SNS) C++

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

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

알고리즘의 분류에 트리, dp 이렇게 적혀 있길래 한참 고민했다. BFS를 이용하여 각 depth마다 최소로 필요한 얼리어답터들을 저장하며 풀었는데 예외상황이 발생했다. 그래서 그냥 dfs에 조건을 넣어서 풀었다.

 

조건

1. 자식에 리프노드가 존재한다면 무조건 얼리어답터가 되야 한다.

2. 자식 중에 얼리어답터가 아닌 사람이 한 명이라도 존재한다면 부모는 얼리어답터가 돼야 한다.

 

dfs로 얼리어답터(파란색)을 찾는 과정

이 조건을 구현하면 부모노드의 갯수는 무조건 자식 노드의 갯수보다 적으므로 최소 얼리어답터의 수가 나오게 된다.

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

int N;
bool check[1000001];
vector<int> v[1000001];
//int dp[1000001][2];
int cnt=0;
bool dfs(int start){
    check[start]=true;
    int size=v[start].size();
    bool flag=false,involve=false;
    for(int i=0;i<size;i++){
        int go=v[start][i];
        if(!check[go]){
            flag=true;
            bool b=dfs(go);
            if(!involve) involve=b;// 자식들 중에 얼리어답터가 아닌 사람이 있다면 무조건 얼리어답터가 돼야 한다.
        }
    }
    if(!flag) return true; //리프노드라면 부모는 무조건 얼리어답터
    if(involve){
        cnt++;
        return false;
    }
    return true;
}


int main(){
    cin>>N;
    int go,to;
    for(int i=0;i<N-1;i++){
        cin>>go>>to;
        v[go].push_back(to);
        v[to].push_back(go);
    }
    dfs(1);
    cout<<cnt;
    return 0;
}