트리 1068

문제 링크

시작점이 상관없는 그래프와 달리 트리는 루트노드부터 탐색하는 것이 수월한 편이다.
리프노드는 there가 없는 노드라고 생각하면 된다.

#include<bits/stdc++.h>
using namespace std;

int n, r, temp, root;
vector<int> adj[54];

// 리프노드 수를 구하는 함수
int dfs(int here){
    int ret = 0; // 리프노드 수
    int child = 0;
    for(int there : adj[here]){
        if(there == r) continue; // 벡터에서 erase까지 하진 않고 탐색을 스킵해준다
        ret += dfs(there);
        child++;
    }
    if(child == 0) return 1;
    return ret;
}

int main(){
    ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
    
    cin >> n; // 트리의 노드의 개수 (N은 50보다 작거나 같은 자연수)
    for(int i = 0; i < n; i++){
        cin >> temp; // 각 노드의 부모. 부모가 없다면 -1
        if(temp == -1) root = i;
        else adj[temp].push_back(i);
    }
    
    cin >> r; // 지울 노드의 번호
    
    if(r == root){
        cout << 0 << "\n";return 0;
    }
    
    cout << dfs(root) << "\n";
    return 0;
}