[BOJ알고리즘, C++]#2533_사회망 서비스, 트리, DP

 

#1. 문제

2533번: 사회망 서비스(SNS)

 

---

 

#2. 풀이

 

1. 트리

[자료구조]#5_트리

 

트리는 1:N 관계의 계층 구조를 갖는 비 선형 자료구조입니다. 트리는 노드와 간선으로 구성되며, 노드 간의 연결 관계를 간선을 통해 나타냅니다. 트리는 그래프의 한 종류로 계층 구조를 형성하며, 비순환 구조를 갖습니다.

 

2. DP, 동적 계획법

[알고리즘]#5_동적 계획법

 

동적 계획법은 최적화 문제를 해결하는 데 사용되는 알고리즘 디자인 기법 중 하나입니다. 동적 계획법은 입력 크기에 따라 중복되는 하위 문제를 재귀적으로 해결하고, 이 결과 값들을 기억하는 것으로 중복 계산을 피해 최적화를 수행하고, 효율적으로 최적해를 찾아냅니다.

 

3. 현재 노드는 EA일 수도, 아닐 수도?

 

1. 먼저, 문제를 해석하자면, 트리의 현재 노드는 EA일 수도, 아닐 수 도 있습니다.
2. 이때, 현재 노드가 EA라면, 자식 노드는 EA일 수도, 아닐 수도 있습니다. 하지만, 현재 노드가 EA가 아니라면, 자식 노드는 무조건 EA입니다.
3. 트리의 루트 노드를 시작으로 DFS를 수행하며, 각 정점에 대하여 두 개의 DP 값을 기억합니다. 하나는  현재 정점이 EA가 아닐 경우의 DP값으로, 현재 정점과 연결된 자식 노드를 순회하며 자식 노드들이 EA일 경우의 DP값을 모두 더해줍니다. 반대로, 현재 노드가 EA일 경우, 자식 노드들이 EA일 경우, 그리고 EA가 아닐 경우의 DP값 중 최소 값을 모두 더해줍니다.
4. 결과적으로, 루트 노드에 쌓인 두 가지 DP 값 중 최소 값을 결과 값으로 출력해줍니다.

 

---

 

#3. 코드

 

#include <iostream>
#include <vector>
using namespace std;

int N;
vector<vector<int>> tree;
vector<vector<int>> dp;
vector<bool> visited;

void dfs(int cur)
{
    visited[cur] = true;
    dp[cur][0] = 0;
    dp[cur][1] = 1;

    for (const auto &node : tree[cur])
    {
        if (visited[node])
            continue;
        dfs(node);
        // #1. 첫 번째 조건, 현재 노드가 얼리어답터가 아닐 경우, 그 자식 노드들은 무조건 얼리어답터
        dp[cur][0] += dp[node][1];
        // #2. 두 번째 조건, 현재 노드가 얼리어답터일 경우, 그 자식 노드들은 얼리 어답터 일 수도, 아닐 수도 있음
        dp[cur][1] += min(dp[node][0], dp[node][1]);
    }
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    cin >> N;

    tree.resize(N + 1);
    dp.resize(N + 1, vector<int>(2));
    visited.resize(N + 1, false);

    for (int i = 0; i < N - 1; ++i)
    {
        int u, v;

        cin >> u >> v;
        tree[u].push_back(v);
        tree[v].push_back(u);
    }

    // #1. DFS 수행을 통해 총 얼리 어답터 수 체크
    dfs(1);

    // #2. dp[1][0] 과 dp[1][1] 중 최소값을 출력
    cout << min(dp[1][0], dp[1][1]);

    return 0;
}

 

---