문제

1. 첫 번째 줄에 전체 node 수 N이 주어짐 (N<=50)
2. 두 번째 줄에 각 node의 parent node index가 주어짐
3. 세 번째 줄에 제거할 node의 index가 주어짐
4. leaf node의 수를 계산해서 반환

---

접근방법 및 주의사항

정석대로 접근하기

1. 전체 node 수를 받아 배열 생성
2. 반복하며 배열에 값을 입력받음
3. 입력받은 값을 바탕으로 tree 생성
4. tree에서 입력받은 node 제거
5. depth first search 방식으로 leaf node 수 계산

주의사항

1. root를 제거한 경우 0을 반환해야 함
2. 문제에 없는 내용을 속단하지 말 것
   • binary tree라는 보장이 없음
   • 입력이 순서대로 들어온다는 보장이 없음

---

문제 풀이

tree node 생성하기

1. binary tree라는 보장이 없으므로 child node의 수를 알 수 없음
   • child node를 linked list 형태로 관리하여 해결
   • head, next, tail을 다룰 포인터를 만듬
2. child node counter를 이용해 leaf node 여부 판별

tree 생성하기

1. 반복문을 돌며 현재 node를 기준으로 parent node를 설정함
   • root node인 경우 parent node index가 -1이므로 넘어감
2. parent node의 child node 목록에 자신을 등록함
   • 첫 번째 child node인 경우 child_head에 등록함
   • 첫 번째 child node가 아닌 경우 child_tail의 다음 node로 등록함
3. 자신을 parent node의 가장 마지막 node로 설정함
4. parent node의 child node 수를 증가시킴

depth first search

1. child node가 없는 경우 leaf node이므로 1을 반환함
2. child node가 있는 경우 child node list의 각 node에 대하여 dfs() function을 적용하고 그 결과를 누적해서 반환함

노드 제거

1. root node를 제거하려는 경우 leaf node 수를 0으로 반환함
2. parent node의 child node list에서 지정한 node만 제거함
3. 제거 후 dfs() function을 이용하여 leaf node의 수를 계산하여 반환함