[백준/BOJ] 백준 1068번 : 트리

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

1068번: 트리

부모 노드와 자식 노드의 관계를 나타내는 ischild를 토대로 트리를 만들고, delete_number노드를 지운 뒤, leaf노드의 개수를 구한다. 여기서 주의해야 될 점은 A노드의 자식 노드가 하나인데 그 자식 노드를 지우면 A노드가 leaf노드가 된다는 점이다.

 

코드

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

int n;
bool ischild[50][50];

struct treenode
{
	int number;
	vector<treenode*> children;
};

treenode* makeTree(int root)
{
	treenode* ret = new treenode();
	ret->number = root;

	//전체 노드중 자식 노드인것에 대해 트리를 만들고 그것을 children에 저장한다
	for (int i = 0; i < n; i++)
		if (ischild[root][i])
			ret->children.push_back(makeTree(i));
	return ret;
}

bool deleteNode(treenode* root, int delete_number)
{
	if (root->number == delete_number)
	{
		//number를 -1이라고 해서 지운 노드라고 표시
		root->number = -1;
		return true;
	}

	else
	{
		for (int i = 0; i < root->children.size(); i++)
		{
			//deleteNode가 true를 반환하면 delete_number노드를 지운것이다
			if (deleteNode(root->children[i], delete_number))
				break;
		}
	}

	return false;
}

int findLeafnum(treenode* root)
{
	//number가 -1이면 지운 노드이다
	if (root->number == -1)
		return 0;

	//leaf노드일때
	if (root->children.size() == 0)
		return 1;

	//만약 자식노드가 하나인데 그 자식 노드가 지워진 거라면 자신이 leaf이다
	if (root->children.size() == 1 && root->children[0]->number == -1)
		return 1;

	int ret = 0;

	//자식노드들을 돌며 전체 leaf노드 개수를 구한다
	for (int i = 0; i < root->children.size(); i++)
	{
		ret += findLeafnum(root->children[i]);
	}

	return ret;
}

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

	memset(ischild, false, sizeof(ischild));

	treenode* root;
	int root_number;
	int delete_number;
	int leaf_num;
	int temp;
	bool return_deleteNode; //deleteNode함수의 반환 값을 받는다 (노드를 성공적으로 지웠다면 true를 반환한다 여기서 return_deleteNode는 큰 의미는 없음 그냥 반환한 값을 받는것)

	cin >> n;

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

		if (temp == -1)
		{
			root_number = i;
		}

		else
		{
			//temp가 i의 부모노드라는것 체크
			ischild[temp][i] = true;
		}
	}

	cin >> delete_number;

	root = makeTree(root_number); //트리 생성
	return_deleteNode = deleteNode(root, delete_number); //delete_number노드를 지운다 (노드를 성공적으로 지웠다면 true를 반환한다 여기서 return_deleteNode는 큰 의미는 없음 그냥 반환한 값을 받는것)
	leaf_num = findLeafnum(root); //leaf노드의 개수를 구한다

	cout << leaf_num;

	return 0;
}