https://www.acmicpc.net/problem/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;
}
'algorithm' 카테고리의 다른 글
16888 루트 게임 (0) | 2022.05.15 |
---|---|
15877 (0) | 2022.05.14 |
휴게소 세우기 (0) | 2022.05.11 |
보석 도둑 (0) | 2022.05.09 |
11000 , 2149 (0) | 2022.03.30 |