출처: https://3months.tistory.com/307 [Deep Play]

백준/DFS,BFS

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

코딩하는 랄뚜기 2021. 8. 11. 12:58

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

 

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

페이스북, 트위터, 카카오톡과 같은 사회망 서비스(SNS)가 널리 사용됨에 따라, 사회망을 통하여 사람들이 어떻게 새로운 아이디어를 받아들이게 되는가를 이해하는 문제가 중요해졌다. 사회망

www.acmicpc.net

알고리즘의 분류에 트리, 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;
}

'백준 > DFS,BFS' 카테고리의 다른 글

[BOJ] 13023 ABCDE  (0) 2021.09.06
[BOJ] 벽 부수고 이동하기 4  (0) 2021.08.30
[BOJ] 14442 벽 부수고 이동하기 2  (0) 2021.08.30
[BOJ] 2234 성곽 C++  (0) 2021.08.14
[BOJ] 2251 물통 C++  (0) 2021.08.01