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

문제

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

걸린 시간

- 실패

풀이

C++

#include <bits/stdc++.h>
#define INF 1e9
typedef long long ll;
typedef unsigned long long ull;
using namespace std;

int n, u, v;
int cache[2][1000001];
set<int> adj[1000001];

int dp(int early, int here){
    // 기저 사례
    if(adj[here].size() == 0){
        if(early) return 1;
        else return 0;
    }
    // 메모이제이션
    int& ret = cache[early][here];
    if(ret != -1) return ret;
    // 재귀 호출
    ret = 0;
    for(auto it = adj[here].begin(); it != adj[here].end(); it++){
        int next = *it;
        if(early) ret += min(dp(1, next), dp(0, next));
        else ret += dp(1, next);
    }
    if(early) ret += 1;
    return ret;
}

void makeTree(){
    queue<int> q;
    q.push(1);
    while(!q.empty()){
        int size = q.size();
        for(int i = 0; i < size; i++){
            int v = q.front();
            q.pop();
            for(auto it = adj[v].begin(); it != adj[v].end(); it++){
                int w = *it;
                adj[w].erase(adj[w].find(v));
                q.push(w);
            }
        }
    }
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cin >> n;
    for(int i = 0; i < n-1; i++){
        cin >> u >> v;
        adj[u].insert(v);
        adj[v].insert(u);
    }
    memset(cache, -1, sizeof(cache));
    makeTree();
    cout << min(dp(0, 1), dp(1, 1));
    return 0;
}

친구관계는 항상 트리 구조로 주어지기 때문에 어느 정점에서 시작해도 트리 형태가 유지된다.

친구 관계가 주어지면 양방향으로 연결한 후, 한 정점을 루트 노드로 가정하고 트리의 진행 방향과 반대인 edge 를 모두 제거하면 얼리 어답터의 개수를 세기 위한 준비가 끝난다. (입력을 받으며 루트 노드를 찾는 방법도 있지만 구현이 번거로워진다.)

사람들의 상태는 얼리 어답터이거나 얼리 어답터가 아닐 수 있다. 자신의 상태에 따라 자신의 친구들의 상태를 두 가지 경우로 나눌 수 있는데, 첫 번째로 자신이 얼리어답터라면 이미 아이디어를 받아들인 상태이기 때문에 자신의 모든 친구들이 얼리어답터인지는 따져보지 않아도 된다. 즉, 얼리 어답터인 사람과 얼리 어답터가 아닌 사람 두 가지 경우가 모두 올 수 있다. 두 번째로 자신이 얼리어답터가 아니라면 아이디어를 받아들이기 위해서는 자신의 모든 친구들이 항상 얼리 어답터이어야만 한다.

이대로 완전탐색을 진행하면 시간초과가 발생한다. 사이클이 없을 뿐이지 내 친구가 다른 사람의 친구가 될 수 있기 때문이다. 여기서 발생한 중복을 제거하기 위해선 현재 상태와 트리의 정점을 쌍으로 최소 인원의 얼리어답터를 메모이제이션하면 된다.