<백준> 1068

트리

문제

입력
첫째 줄에 트리의 노드의 개수 N이 주어진다. N은 50보다 작거나 같은 자연수이다. 둘째 줄에는 0번 노드부터 N-1번 노드까지, 각 노드의 부모가 주어진다. 만약 부모가 없다면 (루트) -1이 주어진다. 셋째 줄에는 지울 노드의 번호가 주어진다.

출력
첫째 줄에 입력으로 주어진 트리에서 입력으로 주어진 노드를 지웠을 때, 리프 노드의 개수를 출력한다.

int n;
vector<vector<int>> tree;
vector<bool> visited;
int deleteNode = 0;
int answer = 0;

void DFS(int num)
{
	visited[num] = true;
	int leaf = 0;

	for (int i : tree[num])
	{
		if (!visited[i] && i != deleteNode)
		{
			leaf++;
			DFS(i);
		}
	}
	if (leaf == 0)
		answer++;
}

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

	cin >> n;

	tree.resize(n + 1);
	visited.resize(n + 1);
	int root = 0;

	for (int i = 0; i < n; i++)
	{
		int node;
		cin >> node;

		if (node != -1)
		{
			tree[node].push_back(i);
			tree[i].push_back(node);
		}
		else
		{
			root = i;
		}
	}

	cin >> deleteNode;

	if (deleteNode == root)
		cout << 0 << "\n";
	else
	{
		DFS(root);
		cout << answer << "\n";
	}
}