문제 설명을 통해 DFS 해결 방식을 생각해내고 리프노드 조건을 잘 정의하였으면 쉽게 해결 할 수 있는 문제였다.

해당 문제에서는 2가지 조건으로 리프노드를 검사하였다.

1. 현재 노드의 사이즈가 0인 경우. 즉 현재 자식노드가 없는 리프노드인지를 확인한다.

if(v[in].size())

2. 다음 노드가 지워야 할 노드인 out_node에 속하고 현재 나에게 자식노드가 out_node 밖에 없다면 현재 나자신은 reaf_node이다.

그리고 현재 자신의 자식이 out_node가 아니더라도 solve(v[in][i])를 통해 다른 자식은 이미 재귀를 보냈기 때문에 연속적인 탐색이 가능하고 다른 자식들에 대해서는 위와 같은 과정이 반복되면서 reaf_node를 찾아낸다.

for (int i = 0; i < v[in].size(); i++) {
        int tmp = solve(v[in][i]);
        if (tmp == -1 && v[in].size() == 1) {
            reaf_node++;
        }
    } 

정답 코드

#include <iostream>
#include <cstring>
#include <algorithm>
#include <queue>

#define endl "\n"

using namespace std;
int n, k;

vector<int> v[51];

int root_node;
int out_node;
int reaf_node = 0;


void input() {
    cin >> n;

    for (int i = 0; i < n; i++) {
        int a;
        cin >> a;
        if (a == -1) {
            root_node = i;
        }
        else {
            v[a].push_back(i);
        }
    }

    //out node
    cin >> out_node;

}

int solve(int in) {
    if (in == out_node) return -1;
    if (!v[in].size()) {
        reaf_node++;
        return 0;
    }
    for (int i = 0; i < v[in].size(); i++) {
        int tmp = solve(v[in][i]);
        if (tmp == -1 && v[in].size() == 1) {
            reaf_node++;
        }
    } 
    return 0;
}

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

    input();C
    solve(root_node);
    cout << reaf_node << endl;
    return 0;
}