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

이 문제는 풀지 못해서, 구글링을 통해서 문제를 해결했다.

 

 

 

문제에 명시적으로 나타나지 않은 부분이 있다면, Root는 항상 1번으로 표현된다는 것이다.

 

 

 

 

위의 그림을 통해서, Root Node가 1번이라는 것을 표현해주고 싶었다고 생각하면 그럴듯하다...

 

 

 

무튼, Root가 1번이므로, 주어진 관계를 이용해서, 트리구조로 변형해야 한다.

 

 

 

어떤 노드들을 선택해야 최소의 얼리어답터를 구할지 모르기 때문에, 전체탐색이 필요하다. 

 

 

 

전체 탐색을 할 때, 메모이제이션을 통해서 DP를 사용할 것이다.

 

 

 

DP[i][j] = i번째 Node, 얼리어답터의 유무(j)에 대한 최소 선택 얼리어답터 수

 

 

 

을 식으로 사용할 것이다. 현재 노드가 얼리어답터인지 아닌지에 따라서, 호출되어야 할 함수가 다르다.

 

 

 

추가적으로 참고해야 할 사항은, 입출력이다. 입력으로 들어오는 노드는 N - 2개이다. 이 부분때문에 다소 시간을 낭비했다.

 

 

 

해설코드(C++).

 

#include <iostream>
#include <vector>
#include <cstring>
#include <algorithm>
 
using namespace std;
 
int N, a, b;
int dp[1000001][2];
vector<int> v[1000001];
vector<int> g[1000001];
 
void dfs(int cur, int pre){
    for(auto nxt : v[cur]){
        if(pre != nxt){
            g[cur].push_back(nxt);
            dfs(nxt, cur);
        }
    }
}
 
int func(int cur, int flag){
    if(dp[cur][flag] != -1)
        return dp[cur][flag];
        
    dp[cur][flag] = 0;
    if(flag){
        for(auto nxt : g[cur]){
            int res1 = func(nxt, 1);
            int res2 = func(nxt, 0);
            dp[cur][flag] += min(res1, res2);
        }
        dp[cur][flag]++;
    }else{
        for(auto nxt : g[cur]){
            dp[cur][flag] += func(nxt, 1);
        }
    }
    
    return dp[cur][flag];
}
 
int main() {
    cin >> N;
    for(int i = 1; i <= N - 1;i++){
        cin >> a >> b;
        v[a].push_back(b);
        v[b].push_back(a);
    }
    
    dfs(1, 0);
    memset(dp, -1, sizeof(dp));
    
    cout << min(func(1, 0), func(1, 1)) << endl;
    return 0;
}