백준 2533 사회망 서비스(SNS)

문제링크 : https://www.acmicpc.net/problem/2533

아이디어

• 브루트포스 : 모든 노드 순회하면서 얼리어답터 O,X 인경우 모두 확인해줌
  • 시간복잡도 : O(2^N) > 시간초과
• 자식의 얼리어답터 최소값을 부모가 활용가능 > tree dp 사용
• DP[node][0] : 얼리어답터 아닐떄 필요한 최소 얼리어답터 수
• DP[node][1] : 얼리어답터일때 필요한 최소 얼리어답터 수
• 부모노드가 얼리어답터 아닐떄 자식노드는 얼리어답터일떄의 합
• 부모노드가 얼리어답터일떄 자식노드는 얼리어답터이거나 아닐때 더 작은값의 합
• 점화식 :
  • DP[node][0] = sum(DP[자식노드][1]
  • DP[node][1] = sum(min(DP[자식노드][0], DP[자식노드][1]))

시간복잡도 계산

• O(노드개수 * 2) = 2e6 > 가능

자료구조

• 인접 리스트 : vector adj[1000010]
• 단방향 리스트 : vector tree[1000010]
  • tree dp 사용할 떄는 단방향 리스트 만들어줘야함
• int dp[1000010][2]
  • DP 최대값 : 1e6 > 가능

코드(C++)

#include <iostream>
#include <vector>
 
using namespace std;
 
vector<int> adj[1000010];
vector<int> tree[1000010];
int dp[1000010][2];
int N;
 
void make_tree(int cur, int pre) {
    for(int x : adj[cur]) {
        if(x==pre) continue;
        tree[cur].push_back(x);
        make_tree(x, cur);
    }
}
 
int get_dp(int node, int early) {
    if(dp[node][early] != -1) return dp[node][early];
    
    int ans=0;
    for(int x : tree[node]) {
        if(early == 0) ans += get_dp(x,1);
        else ans += min(get_dp(x,1), get_dp(x,0));
    }
    
    return dp[node][early] = ans + early;
    
}
 
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    
    // tree dp는 root에서부터 top-down으로 이루어짐
    // 그래서 -1로 초기화
    fill(&dp[0][0], &dp[1000009][2], -1);
    
    cin >> N;
    for(int i=0; i<N-1; i++) {
        int a,b; cin >> a >> b;
        adj[a].push_back(b);
        adj[b].push_back(a);
    }
    
    // 단방향 그래프로 바꿔줌
    make_tree(1, -1);
    
    // root 노드에서 얼리 어답터 최소 수를 구하기
    cout << min(get_dp(1,0), get_dp(1,1)) << '\n';
    return 0;
}
 

문제유형

• DP - Tree DP
  • 자식노드의 값을 재활용 할 수 있을 때 Tree DP 사용 가능
  • 기존의 DP와 다른점은, 간선으로 연결된 노드에 DP를 적용

비슷한 문제

• https://www.acmicpc.net/problem/1693