[BOJ/C++] 1068 트리

리프 노드의 개수를 구하는 문제로 DFS를 이용해 문제를 해결할 수 있습니다.

1. 모든 노드를 탐색하며 리프 노드가 없으면 결과값 1증가
2. 만약 삭제된 노드라면 탐색 중지
3. 삭제한 노드가 루트 노드라면 탐색할 수 없으므로 0 출력

#include <iostream>
#include <cmath>
#include <algorithm>
#include <vector>
#include <stack>
#include <deque>
#include <queue>
#include <string>
#include <climits>

using namespace std;

using int32 = long;
using int64 = long long;

static vector<vector<int>> G;
static vector<bool> visited;

static int deleteNode;
static int result = 0;

void DFS(int node);

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);

    int N;
    int rootNode=0;

    cin >> N;
    G.resize(N);
    visited.resize(N, false);

    for(int i=0; i<N; i++)
    {
        int temp;
        cin >> temp;

        if (temp == -1)
            rootNode = i;
        else
        {
            G[i].push_back(temp);
            G[temp].push_back(i);
        }
    }

	cin >> deleteNode;

    if (deleteNode == rootNode)
    {
        cout << 0;
        return 0;
    }

    visited[rootNode] = true;
	DFS(rootNode);

    cout << result;

    return 0;
}

void DFS(int node)
{
    int leafNode = 0;

    for(const int next : G[node])
    {
	    if(!visited[next] && next!=deleteNode)
	    {
            visited[next] = true;
            leafNode++;
            DFS(next);
	    }
    }

    if (leafNode == 0)
        result++;
}