[BOJ 2533 | C++] 사회망 서비스(SNS) :: Tree DP

• 문제 링크 : https://www.acmicpc.net/problem/2533
• 문제 태그 : 다이나믹 프로그래밍, 트리, 트리에서의 다이나믹 프로그래밍
• 참고 자료 : https://devvidea.tistory.com/4

BOJ 2533 (사회망 서비스(SNS)) - CT 풀이

 

풀이

솔직히 로직을 생각해내기 어려워서 첨부한 블로그의 CT 풀이를 참고하여 구현했습니다.

 

우선 DP를 활용하려면 적절한 DP 테이블을 정의하는 것이 중요합니다. 이 문제에서는 2차원 DP 배열을 사용해야 합니다. 

• 행 : 노드의 번호
• 열 : 해당 노드의 사람이 얼리 아답터인지 여부 (0: 아님, 1: 얼리 아답터)

 

문제에서 "얼리 아답터가 아닌 사람들은 자신의 모든 친구들이 얼리 아답터일 때만 아이디어를 받아들인다." 라는 조건을 통해 모든 사람에게 아이디어를 퍼뜨리려면 다음과 같은 규칙이 필요합니다.

 

1. 얼리 아답터가 아닌 사람은 반드시 인접한 친구 중 얼리 아답터가 있어야 합니다.
2. 얼리 아답터인 사람은 주변에 얼리 아답터가 있는지 없는지 상관없습니다.

 

다음으로 코드에서 루트를 1로 잡았는데 루트 노드는 아무 정점으로 잡아도 상관없습니다.

만약 루트를 2로 설정하는 경우, dfs(2)를 호출하고 마지막에 min(dp[2][0], dp[2][1])을 출력하면 됩니다. 

 

코드

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

vector<vector<int>>dp;
vector<vector<int>>g;
vector<int> seen;

void dfs(int cur) {
    if (seen[cur]) return;
    seen[cur] = true;
    dp[cur][0] = 0;
    dp[cur][1] = 1;

    for (auto nxt : g[cur]) {
        if (seen[nxt]) continue;
        dfs(nxt);
        dp[cur][0] += dp[nxt][1];
        dp[cur][1] += min(dp[nxt][0], dp[nxt][1]);
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    int n;
    cin >> n;

    dp.resize(n + 1, vector<int>(2, 0));
    g.resize(n + 1);
    seen.resize(n + 1, false);

    for (int i = 0;i < n - 1;i++) {
        int a, b;
        cin >> a >> b;
        g[a].push_back(b);
        g[b].push_back(a);
    }

    dfs(1);

    cout << min(dp[1][0], dp[1][1]);
}