BOJ 백준 1068 트리

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

< 트리 >

 트리가 주어지고 삭제할 노드를 정해주었을 때, ( 삭제한 노드의 자식노드들도 삭제되는 것으로 간주 )

 그 트리의 리프 노드의 개수를 구하는 문제이다.

 C++을 공부하고 있어서 인지 class를 이용하여 풀고 싶었다.

Node class의 멤버 변수, 함수들 ******************************************

Node* parent : 부모 노드 ( 부모 노드는 단 한 개 )

Node* child[SIZE] : 자식 노드들 ( 여러 개일 수 있기 때문에 배열로 선언 )

int     n_size : 자식 노드의 인덱스 및 개수

bool  deleted : 자신이 삭제된 노드인지 아닌지를 표시할 bool 변수

int number : 자신이 몇 번 노드인지 나타내는 변수

bool isLeaf(); : 자신이 리프 노드인지를 알려줄 함수

************************************************************************

이 클래스의 리스트인 nodeList[SIZE]에 입력되는 노드들을 저장해주고,

delete_node() 함수를 통해, 삭제할 노드로 지정된 노드와, 그의 자식 노드들을 타고 들어가 deleted 변수를 true로 해준다.

삭제할 때, 자신의 부모 노드의 자식 사이즈를 감소시켜준다.

자식 사이즈가 0개이고 삭제된 노드가 아니라면, 리프 노드로 본다.

=> 이 문제 풀이는, 노드를 실제로 삭제하는 것도 아니고 삭제되는 노드가 무엇인지 보지 않고 단순 부모 노드의

자식 수만 감소시키는, 단순 문제를 풀기 위한 코딩으로 좋은 문제 풀이는 아니라고 할 수 있다.

#include <iostream>
#include <cstring>
#define SIZE 51

using namespace std;

class Node {
public:
	Node* parent;
	Node* child[SIZE];
	int n_size;
	bool deleted;
	int number;

	Node() : n_size(0), parent(NULL), deleted(false), number(0) {}

	bool isLeaf() {
		if (n_size <= 0 && !deleted) return true;
		return false;
	}
};

Node nodeList[SIZE];

void delete_node(Node* node) {
	node->deleted = true;
	node->parent->n_size--;

	int n_size = node->n_size;
	for (int i = 0; i < n_size; i++) {
		delete_node(node->child[i]);
	}
}

int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);

	int n;
	cin >> n;

	int p;
	int root_num = 0;
	for (int i = 0; i < n; i++) {
		cin >> p;
		if (p != -1) {
			nodeList[i].parent = &nodeList[p];
			nodeList[p].child[nodeList[p].n_size++] = &nodeList[i];
		}
		else {
			root_num = i;
		}
		nodeList[i].number = i;
	}
	int del_node;
	cin >> del_node;
	if (del_node == root_num) {
		cout << "0" << '\n';
		return 0;
	}


	delete_node(&nodeList[del_node]);

	int count = 0;
	for (int i = 0; i < n; i++) {
		if (nodeList[i].isLeaf()) count++;
	}

	cout << count << '\n';

	return 0;
}