[C++] 백준 1068번 트리

트리에서 하나의 노드를 지웠을 때 루트노드의 개수를 구하는 문제입니다.
노드를 지웠을때 그 노드의 자식노드도 같이 지워집니다.

2차원 벡터 2개를 생성했습니다.
vector<vector<int> > p 부모 노드값 저장    ex) p[i][0] i의 0번째 부모
vector<vector<int> > c 자식 노드값 저장    ex) c[i][0] i의 0번째 자식

지우려는 노드의 부모 노드로 가서
연결된 자식노드(삭제하려는 노드)를 지워줍니다.
연결선이 끊겼으므로, 삭제된 노드의 자식노드와의 연결도 끊기게 됩니다.

그리고 최상위 노드에서 DFS를 통해서 리프노드들을 탐색해서 개수를 출력해줍니다.

 

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

int n;
int num;
int del;
int start;
vector<vector<int> > p;
vector<vector<int> > c;

int DFS(int a)
{
	int count = 0;

	if (c[a].size() == 0) {
		return 1;
	}

	for (int i = 0; i < c[a].size(); ++i) {
		count += DFS(c[a][i]);
	}

	return count;
}

int main(int argc, char *argv[]) 
{
	cin >> n;

	p.resize(n);
	c.resize(n);
	
	for (int i = 0; i < n; ++i) {
		cin >> num;
		
		if (num == -1) {
			start = i;
			continue;
		}

		p[i].push_back(num);
		c[num].push_back(i);
	}

	cin >> del;

	if (p[del].size() == 0) {
		cout << "0" << endl;
		return 0;
	}

	int parent = p[del][0];
	for (int i = 0; i < c[parent].size(); ++i) {
		if (c[parent][i] == del) {
			c[parent].erase(c[parent].begin() + i);
			break;
		}
	}

	cout << DFS(start) << endl;
	
	return 0;
}