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

문제 설명

풀이 방법

이 문제는 트리에서 dp를 이용하는 문제이다.

dp[현재 노드][현재 노드가 얼리어답터인가 여부]로 dp테이블을 만들고 현재 노드가 얼리어답터가 아니라면 자식노드는 항상 얼리어답터이고, 얼리어답터라면 얼리어답터일수도, 아닐수도 있다.

이 문제는 이 문제 와 매우 비슷하여 쉽게 해결하였다.

코드

#include <bits/stdc++.h>

using namespace std;

vector<vector<int>> v, tree;
int dp[1000006][2];
bool visited[1000006];

//단방향 그래프로 바꾼다
void dfs(int cur) {
    if (visited[cur]) return;
    visited[cur] = true;
    for (auto nxt : v[cur]) {
        if (!visited[nxt]) {
            tree[cur].push_back(nxt);
            dfs(nxt);
        }
    }
}

int dpf(int cur, int include) {
    int &res = dp[cur][include];
    if (res != -1) return res;
    //현재 노드가 얼리어답터일 경우
    if (include) {
        int ans = 1;
        for (auto nxt : tree[cur]) {
            ans += min(dpf(nxt, 0), dpf(nxt, 1));
        }
        return res = ans;
    //현재 노드가 얼리어답터가 아닌 경우
    } else {
        int ans = 0;
        for (auto nxt : tree[cur]) {
            ans += dpf(nxt, 1);
        }
        return res = ans;
    }
}

int main() {
    int N; scanf("%d", &N);
    v.resize(N + 1);
    tree.resize(N + 1);
    for (int i = 1; i <= N; i++) {
        int a, b; scanf("%d %d", &a, &b);
        v[a].push_back(b); v[b].push_back(a);
        dp[i][0] = dp[i][1] = -1;
    }
    dfs(1);
    printf("%d", min(dpf(1, 0), dpf(1, 1)));
}

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