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

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

• 괜히 어렵게 풀었다는 감이 있어 나중에 실력을 더 키워서 지금보다 쉽게 풀어보고 싶은 문제
• 하나 실수했던 점은, delNode 함수에서 Node를 참조 설정하지 않아 isDel 변수의 변화를 제대로 전달하지 못하게 됨. 초보적인 실수이므로 이 점은 다시 유의할 것

1. 트리라는 제목에 맞게 어떻게 자료구조를 구현할지 생각
2. 노드를 지우면 그 노드와 노드의 모든 자손이 트리에서 제거된다 -> DFS

#include<iostream>
#include<vector>
using namespace std;
#define MAX 50
int n, del, answer = 0;

struct Node {
	bool isDel = false;
	int par = -1;
	vector<int> child;
}node[MAX + 1];

void input() {
	cin >> n;
	int p;
	for (int i = 1; i <= n; ++i) {
		cin >> p;
		node[i].par = p + 1;
		node[p + 1].child.push_back(i);
	}
	cin >> del;
	++del;
}

void delNode(Node *pNode) {
	if (pNode->isDel == true) return;
	pNode->isDel = true;
	for (int i = 0; i < pNode->child.size(); ++i) {
		delNode(&node[pNode->child[i]]);
	}
	pNode->child.clear();
}

void search(Node pNode) {
	if (pNode.child.empty() && pNode.isDel == false) {
		++answer;
		return;
	}
	for (int i = 0; i < pNode.child.size(); ++i) {
		search(node[pNode.child[i]]);
	}
}

void solution() {
	input();
	if (node[node[del].par].child.size() == 1) {
		node[node[del].par].child.clear();
	}
	delNode(&node[del]);
	for (auto i : node[0].child) {
		search(node[i]);
	}
	cout << answer;
}

int main() {
	cin.tie(0), cout.tie(0), ios_base::sync_with_stdio(0);
	solution();
	return 0;
}