[BOJ 2533 // C++] 사회망 서비스(SNS)

※ 글쓴이는 취미로 코딩을 익혀보는 사람이라 정확하지 않은 내용을 담고 있을 수 있다 ※

 

이번에 볼 문제는 백준 2533번 문제인 사회망 서비스(SNS)이다.
문제는 아래 링크를 확인하자.

www.acmicpc.net/problem/2533

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

이 문제를 처음에는 단순히 깊이가 홀수인 노드와 짝수인 노드의 개수 가운데 작은 것을 출력하는 문제로 오해했다.

문제에 주어진 예시 그림이 잘못된 선입견을 준 것이다.

실제로는 단순히 깊이의 홀짝만으로 구분을 해서는 안 된다. 많은 dp문제에서 간격을 최대로 하여 움직여서 문제를 해결하지 못하는 것과 같은 원리이다.

 

따라서 이 문제는, 루트를 하나 정하고, 각 노드를 루트로 하는 부분트리에 대하여 이 노드가 early adapter인 경우와 아닌 경우의 (부분트리에서의) early adapter이 필요한 최소 수를 기록해나가는 것으로 해결할 수 있다.

 

아래는 제출한 소스코드이다.

#include <iostream>
#include <vector>
#include <cmath>
using std::cin; using std::cout;
using std::vector;
using std::pair;
using std::min;

int N;
vector<int> G[1000001];

pair<int,int> dfs(int current, int root) {
    int early = 1, late = 0; 
    vector<int>::iterator iter = G[current].begin();
    while (iter != G[current].end()) {
        if (*iter == root) {
            iter++; continue;
        }
        pair<int, int> temp = dfs(*iter, current);
        early += min(temp.first, temp.second);
        late += temp.first;
        iter++;
    }
    return { early,late };
}

int main()
{
    std::ios::sync_with_stdio(0);
    cin.tie(0);

    cin >> N;
    
    int x, y;
    for (int i = 1;i < N;i++) {
        cin >> x >> y;
        G[x].push_back(y);
        G[y].push_back(x);
    }
    pair<int, int> ans = dfs(1, 0);
    cout << min(ans.first, ans.second);
    
    return 0;
}