사회망 서비스

백준 2533번: 사회망 서비스

아이디어

부모가 얼리어답터라면 내가 얼리어답터가 되는 경우와 되지 않는 경우 두 가지를 모두 고려한다. 부모가 얼리어답터가 아니라면 내가 얼리어답터가 되는 경우만 고려하면 된다.

루트 노드부터 내려가면서 모든 케이스를 시도해보고, 그중 최솟값을 메모이제이션 한다. 자신의 모든 자식 노드에 대해 재귀호출 해야 한다.

코드

#include <bits/stdc++.h>

using namespace std;

constexpr int MAX = 1000000;
int N;
int cache[MAX+1][2];
bool visited[MAX+1];
vector<vector<int>> adj(MAX+1), tree(MAX+1);

void dfs(int node) {
    visited[node] = 1;
    for (int x : adj[node]) {
        if (!visited[x]) {
            tree[node].push_back(x);
            dfs(x);
        }
    }
}

int solve(int cur, bool adopter) { // 현재 노드, 부모가 얼리어답터인지
    int& ret = cache[cur][adopter];
    if (ret != -1) return ret;

    ret = MAX;
    int sum;

    if (adopter) { // 부모가 얼리어답터면 현재 노드를 고르지 않아도 됨
        sum = 0;
        for (int x : tree[cur]) {
            sum += solve(x, 0);
        }
        ret = min(ret, sum);
    }

    // 현재 노드를 얼리어답터로 고르는 경우
    sum = 1;
    for (int x : tree[cur]) {
        sum += solve(x, 1);
    }
    ret = min(ret, sum);

    return ret;
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cin >> N;
    for (int i = 0; i < N-1; i++) {
        int u, v;
        cin >> u >> v;
        adj[u].push_back(v);
        adj[v].push_back(u);
    }
    dfs(1);
    memset(cache, -1, sizeof(cache));
    cout << solve(1, 1);
    return 0;
}

여담

입력이 매우 불친절하다. 당연히 루트 노드부터 부모, 자식 순으로 주는 줄 알았는데 그냥 친구관계만 주어진다. 따라서 인접 리스트로 받고, visited배열로 중복을 제거하여 tree를 만들어주면 된다. 루트 노드를 뭘로 하든 상관 없다. 편하게 1로 설정했다.