[백준 1068]트리

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

1) 문제분류

-트리

2)문제 해결

- vector에 부모노드에 연결되어있는 자식노드들을 담아 연결을 시킨다.

- DFS를 통해서 모든 리프노드를 조사를 하는데, 제거할 노드를 만났을때 return 함으로써 그 부분만 탐색을 안하면 된다.

- DFS로 탐색을 할때에는 해당노드의 자식노드들의 개수가 0개라면 Leaf노드이므로 개수를 세어준다.

#include <iostream>

#include <vector>

using namespace std;

vector<int> tree[51];

int n,root,ans, x;

void search(int cur) {

if (cur == x) return;

int ok = 0;

for (int i = 0; i < tree[cur].size();i++)

{

if (tree[cur][i] == x)continue;

search(tree[cur][i]); 

ok++;

}

if (ok == 0) ans++;

}

int main() {

scanf("%d", &n);

for (int i = 0; i < n; i++) {

scanf("%d", &x);

if (x == -1)

{

root = i;

continue;

}

tree[x].push_back(i);

}

scanf("%d", &x);

tree[x].clear();

search(root);

printf("%d\n", ans);

}