[백준] 1068 트리

백준 1068 트리

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

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

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

	int N;
	cin >> N;

	//parent[i]: i노드의 부모 노드 번호
	vector<int> parent(N, -1);
	//valid[i]: i노드 삭제되었는지 존재하는지
	vector<int> valid(N, 1);

	//트리 입력받기
	for (int i = 0; i < N; ++i) {
		int input;
		cin >> input;
		parent[i] = input;
	}

	//삭제할 노드의 번호
	int rm;
	cin >> rm;

	//삭제할 노드들
	queue<int> q;
	q.push(rm);

	while (!q.empty()) {
		int node = q.front();
		q.pop();

		//노드 삭제
		valid[node] = 0;

		//삭제된 노드를 부모로 갖는다면 삭제되어야
		for (int i = 0; i < N; ++i) {
			if (parent[i] == node) {
				q.push(i);
			}
		}
	}

	int leafCnt = 0;
	//자신을 부모로 갖는 노드가 없다면 리프 노드
	for (int i = 0; i < N; ++i) {
		if (!valid[i]) continue;

		bool haveChild = false;
		for (int j = 0; j < N; ++j) {
			if (!valid[j]) continue;

			if (parent[j] == i) {
				haveChild = true;
				break;
			}
		}
		if (!haveChild) leafCnt++;
	}

	cout << leafCnt;
	return 0;
}