[C/C++ 백준 1068번] 트리 (Silver 1)

www.acmicpc.net/problem/1068

1068번: 트리

기본적인 전략은, 1. 모든 leaf Node의 개수를 찾고, 2. 삭제된 노드부터의 모든 leaf Node 개수를 찾아 빼준다. 3. 그리고 삭제된 노드의 부모 노드의 자식노드(==형제 노드)가 없을 경우, 노드가 삭제되면 부모가 leaf Node로 변하기 때문에 하나 더해준다.

 

#include <cstdio>
#include <vector>
#include <queue>
using namespace std;
int N, x, del;
vector <int> v[51];
int find(){
	int ans=0, m=0;
	for(int i=0; i<N; i++){
		if(v[i].size()==0)
			ans++;
	}
	queue <int> q;
	q.push(del);
	while(!q.empty()){
		int tmp = q.front();
		if(v[tmp].size()==0){
			m++;
		}
		else{
			for(int i=0; i<v[tmp].size(); i++)
				q.push(v[tmp][i]);
		}
		q.pop();
	}
	for(int i=0; i<N; i++){
		for(int j=0; j<v[i].size(); j++){
			if(v[i][j]==del && v[i].size()==1)
				return ans-m+1;
		}
	}
	return ans-m;
}
int main(void){
	scanf("%d", &N);
	for(int i=0; i<N; i++){
		scanf("%d", &x);
		if(x!=-1)
			v[x].push_back(i);
	}
	scanf("%d", &del);
	printf("%d", find());
}