문제 푼 날짜 : 2021-10-03

문제

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

접근 및 풀이

Tree에서 DP를 이용하여 푸는 문제였다.
이 문제에서는 Tree의 노드들이 어떤 상태를 갖는지에 대해서 생각해보아야한다.
문제에서는 두 가지 상태가 있다. 얼리어답터냐, 아니냐
따라서 dp 배열을 아래와 같이 정의할 수 있다.

dp[a][0] = c : a 노드를 정점으로 하면서 a가 얼리어답터가 아닐 때, 필요한 최소 얼리어답터 수는 c이다.
dp[a][1] = c : a 노드를 정점으로 하면서 a가 얼리어답터일 때, 필요한 최소 얼리어답터 수는 c이다.

이를 이용해서 dfs로 탐색해주면서 아래의 조건을 유의하면서 각 노드의 상태를 업데이트 해준다.

1. 해당 노드가 얼리어답터가 아닐 경우, 그 다음 친구는 반드시 얼리어답터여야한다.
2. 해당 노드가 얼리어답터인 경우, 그 다음 친구는 얼리어답터여도 되고, 아니어도 된다.
   (이 경우엔 친구가 얼리어답터인 경우와 얼리어답터가 아닌 경우 둘 중에 최솟값을 업데이트해준다.)

코드

// 백준 2533번 : 사회망 서비스(SNS)
#include <iostream>
#include <vector>

using namespace std;

int N;
vector<int> v[1000001];
int dp[1000001][2];
bool visited[1000001];

void dfs(int node) {
    visited[node] = true;
    dp[node][0] = 0; // 해당 노드가 얼리어답터가 아닌 경우
    dp[node][1] = 1; // 해당 노드가 얼리어답터인 경우

    for (auto next : v[node]) {
        if (visited[next]) {
            continue;
        }
        dfs(next);
        dp[node][0] += dp[next][1];
        dp[node][1] += min(dp[next][0], dp[next][1]);
    }
}

int main() {
    cin >> N;

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

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

결과

피드백

많은 고수분들의 풀이와 힌트를 참고한 후에야 풀 수가 있었다.
Tree와 DP,,, 문제를 풀 때마다 DP를 어떻게 설계해야할지 어려워서 인상이 찌푸려지지만, 문제를 풀고 이해하고 나면 이 것만큼 쉬운 게 없다.
많이 많이 풀다보면 나도 어느 순간 DP의 달인이 되어 있지않을까..