1068

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

1068번: 트리

부모 자식 관계만을 이용해서 해결하는 문제

삭제할 때 dfs를 이용해서 쭉 삭제함( p[x] = -2 )

리프노드 : 어떤 노드를 부모로 하는 노드가 없으면 그 노드는 리프 노드이다.

 

//1068
#include <iostream>
#include <cmath>
using namespace std;
int n, ans;
int p[51];
void dfs(int x){
	p[x] = -2; // 삭제
	for(int i = 0; i < n; i++){
		if(p[i] == x) dfs(i);
	}
	
}

int main() {
    int k;
	cin>>n;
	for(int i = 0; i < n; i++)	cin>>p[i];
	cin>>k;
	dfs(k);
	for(int i =0 ; i < n; i++){
		if(p[i] == -2) continue;
		ans++;
		for(int j = 0; j < n ;j++){
			if(p[j] == i) {
				ans--;break;
			}
		}
	
	}
	cout<<ans;
	return 0;
}