[Algorithm Problem] 트리 (BAEKJOON: 1068)

트리 (BAEKJOON: 1068)

이 문제에서는 트리를 구축하고, 노드 하나를 지운 뒤, Leaf 노드 개수를 세는 간단한 기능을 구현한다. 특히 재미있었던 부분은 struct를 이용해 Node 구조체를 선언한 뒤, Leaf 노드 판별을 진행할 때다. 풀이 초반에는 자식 노드의 index 번호를 받아 저장했는데, 이렇게 되면 해당 노드가 지워진 노드인지 판별하기 위한 접근이 struct 외부에서 밖에 구현되지 못 한다.

Object Diagram 상으로 그렸을 때, 특정 노드가 다른 노드에 접근해 해당 노드가 지워진 노드인지 확인하는 작업을 수행하려면 Reference를 알아야 하며, 자연스럽게 구조체 Pointer를 다뤄야 했다. 회사 점심 시간에 여기까지 생각하니 불이 켜졌다.

끝으로 BFS 기반 트리 순회를 수행하기 위해 queue 라이브러리를 사용했는데, 나중에 시간이 남는다면 꼭 자체 구현한 Queue를 활용한 풀이도 올려보려고 한다.

풀이

#include<iostream>
#include<queue>

using namespace std;

struct Node {
	int cnt = 0;
	int excluded = 0;
	Node* child[50];

	void add(Node* c) {
		child[cnt++] = c;
	}

	void set_exclude() {
		this->excluded = 1;
	}

	bool is_excluded() {
		return this->excluded == 1;
	}

	bool is_leaf() {
		if (cnt == 0) return true;

		int ch_cnt = 0;
		for (int i = 0; i < cnt; i++) {
			if (!child[i]->is_excluded()) ch_cnt++;
		}

		if (ch_cnt == 0) return true;
		return false;
	}
} node[50];

int main(int argc, char* argv[]) {
	int N, root, ex, ans = 0;
	cin >> N;

	for (int i = 0; i < N; i++) {
		int prt;
		cin >> prt;

		if (prt == -1) root = i;
		else {
			node[prt].add(&node[i]);
		}
	}

	cin >> ex;
	node[ex].set_exclude();

	queue<Node*> q;
	q.push(&node[root]);

	while (!q.empty()) {
		Node* p = q.front();
		q.pop();

		if (p->is_excluded()) continue;
		if (p->is_leaf()) {
			ans += 1;
			continue;
		}

		for (int i = 0; i < p->cnt; i++) {
			if (p->child[i]->is_excluded()) continue;
			q.push(p->child[i]);
		}
	}

	cout << ans;

	return 0;
}