백준 2533번 : 사회망 서비스(SNS) (C/C++)

<문제>

백준 2533번

 

<풀이>

최소 얼리 어댑터의 수를 구하는 문제이다. 전형적인 트리dp문제라고 볼 수 있다.

이문제를 풀기 위해서는 트리는 트리로 구성되어있다는 개념을 이용해야한다.

 

우선 k=1을 얼리 어댑터, k=0인 경우를 얼리 어댑터가 아닌 경우라고 할때,

dp 배열을 아래와 같이 정의한다.

 

dp[n][k] : n이 k이고, n을 루트로하는 서브트리의 최소 얼리 어댑터의 수

 

1. k=1일때,

  자식 노드들이 1이여도 되고, 0이여도된다. n의 모든 자식 노드를 nx라고 할때, 다음이 성립한다.

 

2. k=0일때,

 모든 자식 노드들이 1이여야만 한다. 

<코드>

#include<bits/stdc++.h>
#define fio()                     \
    ios_base::sync_with_stdio(0); \
    cin.tie(0)
using namespace std;
 
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef tuple<int, int, int> tpi;
typedef tuple<ll, ll, ll> tpl;
typedef pair<double, ll> pdl;
 
const int INF = 0x3f3f3f3f;
const ll IINF = 0x3f3f3f3f3f3f3f3f;
const int dx[] = { 0, 1, 0, -1 };
const int dy[] = { 1, 0, -1, 0 };
 
vector<int> g[1010101];
int dp[1010101][2], depth[1010101];
 
int f(int x, int k, int lev){
    if(dp[x][k] != -1) return dp[x][k];
 
    dp[x][k] = k;
    depth[x] = lev;
    if(k == 1){
        for(auto nx : g[x]){
            if(depth[nx] > lev) dp[x][k] += min(f(nx, 0, lev+1), f(nx, 1, lev+1));
        }
    }
    else{
        for(auto nx : g[x]){
            if(depth[nx] > lev) dp[x][k] += f(nx, 1, lev+1);
        }
    }
    return dp[x][k];
}
 
int main(){
    memset(dp, -1, sizeof(dp));
    memset(depth, INF, sizeof(depth));
    int n; scanf("%d", &n);
    for(int i = 0; i < n-1; i++){
        int u, v; scanf("%d %d", &u, &v);
        g[u].push_back(v);
        g[v].push_back(u);
    }
    printf("%d", min(f(1, 0, 1), f(1, 1, 1)));
}
 

<회고>

트리는 트리로 만들어져 있다는 최적 부분 구조를 이용해볼 수 있는 문제였다.