백준 2533번 사회망 서비스(SNS)[C++]

1. 문제 풀이

 문제 유형은 재귀를 사용한 dfs를 사용하여 풀이했습니다.

 처음 문제를 읽고 얼리어답터를 어떻게 결정하는 것이 좋을지 감이 잡히지 않았습니다. 트리를 직접 그려서 분석해 본 결과 초기 얼리어답터가 되어야 하는 정점은 리프 노드를 자손으로 가지고 있는 정점이라는 사실을 어렵지 않게 도출할 수 있었습니다. 예제 입력 2를 위상으로 확인해 본 결과 자손을 리프 노드로 가지는 정점뿐만 아니라 추가적으로 얼리어답터를 결정해야 합니다. 따라서 현재 정점이 리프 노드를 자손으로 가지는지 여부 판단과 리프 노드를 자손으로 가지고 있진 않으나 얼리어답터로 지정해야 하는 경우를 판단하는 로직으로 크게 분류하여 구현하였습니다.

 우선 리프 노드는 부모 노드와 연결된 간선 1개 만을 가집니다. dfs를 바탕으로 자손노드가 리프노드인지 확인할 수 있습니다. 현재 정점이 리프 노드를 가져 얼리어답터가 된 경우, 현재 정점과 부모 노드의 간선을 끊어 부모 노드가 리프 노드가 되도록 합니다. 이를 통해 부모의 부모 정점이 추가적으로 얼리어답터가 필요한 경우를 파악할 수 있습니다. 그러나 부모 노드가 필요에 의해 이미 얼리어답터가 된 경우 불필요한 얼리어답터가 추가될 수 있어 이를 방지하기 위해 현재 정점이 리프 노드를 가지지 않아야 한다는 조건을 추가하여 반환합니다.

 

2. 코드

#include <bits/stdc++.h>
using namespace std;
typedef long long ll; typedef unsigned long long ull; typedef pair<int,int> pi; typedef pair<ll, ll> pl;
typedef tuple<int, int, int> ti; typedef tuple<ll, ll, ll> tl; typedef vector<int> vi; typedef vector<ll> vl;
typedef vector<pi> vpi; typedef vector<pl> vpl; typedef vector<ti> vti; typedef vector<tl> vtl;
typedef vector<string> vs; typedef vector<bool> vb; typedef queue<int> qi; typedef queue<ll> ql;
typedef queue<pi> qpi; typedef queue<pl> qpl; typedef queue<ti> qti; typedef queue<tl> qtl;
#define fastio(x, y) cin.tie((x))->sync_with_stdio((y))
#define X first
#define Y second
#define pb push_back
#define sz(x) (int((x).size()))
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
const char nl = '\n';

int n;
vi adj[1'000'005];
vb leaf_node(1'000'005);

int ans;

bool dfs(int cur, int prv) {
    // 노드 자손들 중 하나라도 리프 노드인지 검사
    bool has_leaf_node = 0;
    for(auto nxt : adj[cur]) {
        if(nxt != prv) {
            has_leaf_node |= dfs(nxt, cur);
        }
    }
    
    // 리프 노드를 가진 노드는 얼리어답터가 되어야 함.
    // 얼리어답터가 된 경우, 부모 노드가 리프 노드가 됨
    if(has_leaf_node) {
        ans++;
        leaf_node[prv] = 1;
    }

    return leaf_node[cur] && !has_leaf_node;
}

int main() {
    fastio(nullptr, false);

    cin >> n;
    for(int i = 0; i < n - 1; i++) {
        int u, v;
        cin >> u >> v;
        adj[u].pb(v);
        adj[v].pb(u);
    }
    
    for(int i = 1; i <= n; i++) {
        leaf_node[i] = sz(adj[i]) == 1;
    }

    dfs(1, 0);

    cout << ans;
}

 

3. 제출 결과