[BOJ] 1068번 트리 (C++)

https://www.acmicpc.net/problem/1068

1068번: 트리

 

#include <iostream>
#include <vector>
using namespace std;

vector<int> tree[50];
int n, k, root;
int leafcnt = 0;

int dfs(int node){
	if(node == k) return -1;
	if(tree[node].size() == 0){
		leafcnt++;
		return 0;
	}
	for(int i = 0; i < tree[node].size(); i++){
		int tmp = dfs(tree[node][i]);
		if(tmp == -1 && tree[node].size() == 1) leafcnt++;
	}
	return 0;
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	
	cin >> n;
	for(int i = 0; i < n; i++){
		int p;
		cin >> p;
		if(p == -1) root = i;
		else tree[p].push_back(i);
	}
	cin >> k;
	dfs(root);
	cout << leafcnt;
	return 0;
}

 

리프 노드인 경우

1. 자식 노드가 없음

2. 자식 노드가 하나인데 그 자식 노드가 제거됨