[PS] 백준 2533번: 사회망 서비스(SNS)

|

문제

내가 이해한 문제 내용

자신이 얼리어답터가 아니고 자신을 제외한 모든 친구가 얼리어답터 일 경우 자신도 아이디어를 받아들이게 되는데 모든 사람이 아이디어를 받아들이도록 하는 얼리어답터의 최소 사람 수를 구하시오.

접근 방식

처음 DP로 level-order traversal을 써서 접근했지만 같은 레벨에서도 얼리어답터인 경우와 아닌 경우가 나눠질 때가 있었다.

어려웠던 점 & 배운 점

결국 다른 이들의 풀이를 보고 다시 풀어봤는데, DFS로 리프노드까지 내려가서 DP로 풀이하는 것이 가장 명쾌했다. 점화식 자체는 비슷했지만 DFS로 접근하지 못해서 낭패를 본 문제이다. 점화식은 아래와 같다.

$DP[i][0]$= 정점 $i$를 루트로 하는 서브트리의 얼리어답터 최소 사람 수인데 정점 $i$가 얼리어답터인 경우

$DP[i][1]$= 정점 $i$를 루트로 하는 서브트리의 얼리어답터 최소 사람 수인데 정점 $i$가 얼리어답터가 아닌 경우

정점 $i$가 얼리어답터라면 친구가 얼리어답터이든 아니든 상관없기 때문에 둘 중 얼리어답터의 수가 작은 값을 더해주면 되고 정점 $i$가 얼리어답터가 아니라면 친구가 반드시 얼리어답터여야 하기 때문에 곧바로 친구가 얼리어답터인 경우를 더해주면 된다.

시간복잡도

메모이제이션을 하기 때문에 $O(V+E)$

코드

#include <cstdio>
#include <cstring>
#include <vector>
#include <algorithm>
using namespace std;

int n,v1,v2,_level,_node;
int visit[1000001];
int dp[1000001][2];
vector<int> g[1000001];

int dfs(int v, bool early)
{
    visit[v] = 1;

    if(early && dp[v][0]!=-1) return dp[v][0];
    if(!early && dp[v][1]!=-1) return dp[v][1];

    dp[v][0] = 1;
    dp[v][1] = 0;
    for(int i=0; i<g[v].size(); i++){
        int next = g[v][i];
        if(!visit[next]){
            dp[v][0] += min(dfs(next,true),dfs(next,false));
            dp[v][1] += dfs(next,true);
        }
    }
    return early ? dp[v][0] : dp[v][1];
}

int main(void)
{
    scanf("%d",&n);
    n--;
    while(n--){
        scanf("%d%d",&v1,&v2);
        g[v1].push_back(v2);
        g[v2].push_back(v1);
    }
    memset(dp,-1,sizeof(dp));
    printf("%d",min(dfs(1,false),dfs(1,true)));
    return 0;
}