[백준 1068] 트리 (C++)

문제 링크: https://www.acmicpc.net/problem/1068

1068번: 트리

1. 주의할 점

- For문을 최대한 덜 사용하도록 한다.

- 배단 Vector를 통해 자식의 정보를 저장한다

- Boolean 배열을 사용하여 해당 Node가 삭제되었는지 확인한다

 

2. 구현

- 큐를 사용하여 지우려는 Node를 큐에 삽입하고 해당 Node의 Erased 배열값을 True로 설정한다.

- 큐에서 Pop을 통해 얻은 Node 번호에 자식이 있다면 전부 Erased 배열의 값을 True로 전환한다.

- 위의 작업을 모두 마친 이후, 0~N-1까지 Node가 지워지지 않은 노드이며 밑의 자식이 없을 경우(지워진 자식 Node 갯수 == 기존에 가지고 있던 자식 Node의 갯수 ) Result++을 진행한다.

 

#include <vector>
#include <iostream>
#include <algorithm>
#include <queue>
using namespace std;
bool erased[50] = { false, };
vector<int> v[50];
int main() {
	int num, tt, target;
	cin >> num;
	for (int i = 0; i < num; i++) {
		cin >> tt;
		if (tt == -1) continue;
		v[tt].push_back(i);
	}
	cin >> target;
	//해당 Node와 그 밑의 Node들의 erased값을 true로 바꾼다
	queue<int> q;
	q.push(target);
	erased[target] = true;
	while (!q.empty()) {
		int cidx = q.front();
		q.pop();
		for (int i = 0; i < v[cidx].size(); i++) {
			int next = v[cidx][i];
			if (!erased[next]) {
				q.push(next);
				erased[next] = true;
			}
		}
	}
	int result = 0;
	for (int i = 0; i < num; i++) {
		bool leaf = true;
		if (!erased[i]) {
			int cnt = 0;
			for (int j = 0; j < v[i].size(); j++) {
				if (erased[v[i][j]]) cnt++;
			}
			if (cnt == v[i].size())
				result++;
		}
	}
	cout << result;
	system("pause");
	return 0;
}