백준 1068번 트리 C++

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

 

1. root부터 탐색하면서 삭제할 노드의 부모 노드를 알아낸다.

2. 삭제할 노드를 dfs를 이용하여 제일 밑에있는 자식 노드부터 차례로 삭제한다.

3. 2번이 끝났으면 삭제할 노드의 자식들은 모두 삭제가 된 상태이기 때문에 1번에서 파악한 부모 노드를 이용하여 삭제할 노드를 삭제한다.

4.  root부터 탐색하면서 리프 노드의 갯수를 알아낸다.

 

예외) 삭제할 노드가 root노드라면 부모 노드가 없기때문에 0을 출력하고 프로그램을 종료한다.

 

#include <iostream>
#include <string>
#include <vector>
#include <math.h>
#include <algorithm>
#include <utility>
#include <stack>
#include <queue>
#include <math.h>
#include <set>
#include <map>
#include <unordered_map>
#include <unordered_set>

using namespace std;
typedef long long ll;

int n, del;
int cnt = 0;
vector<vector<int>> tree(51, vector<int>());

void DeleteNode(int node) {
	for (auto child : tree[node]) {
		DeleteNode(child);
		auto it = find(tree[node].begin(), tree[node].end(), child);
		tree[node].erase(it);
	}
}

void FindAndDeleteNode(int node) {
	for (auto child : tree[node]) {
		if (child == del) {
			DeleteNode(child);
			auto it = find(tree[node].begin(), tree[node].end(), child);
			tree[node].erase(it);
		}
		FindAndDeleteNode(child);
	}
}

void FindLeafNode(int node) {	
	for (auto child : tree[node]) {
		FindLeafNode(child);
	}
	if (tree[node].size() == 0) cnt++;
}

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

	cin >> n;
	int parent;
	int root;
	for (int i = 0; i < n; i++) {
		cin >> parent;
		if (parent == -1) {
			root = i;
			continue;
		}
		tree[parent].push_back(i);
	}
	cin >> del;
	if (del == root) {
		cout << 0;
		return 0;
	}
	FindAndDeleteNode(root);
	FindLeafNode(root);
	cout << cnt;
};