백준 1068번 트리

문제

트리에서 리프 노드란, 자식의 개수가 0인 노드를 말한다.

트리가 주어졌을 때, 노드 중 하나를 제거할 것이다. 그 때, 남은 트리에서 리프 노드의 개수를 구하는 프로그램을 작성하시오.

예를 들어, 다음과 같은 트리가 있다고 하자.

현재 리프 노드의 개수는 3개이다. (초록색 색칠된 노드) 이때, 1번을 제거한다고 하면, 다음과 같이 된다.

이제 리프 노드의 개수는 1개이다.

문제풀이

사용한 알고리즘: DFS

(1) 코드 7~18

 Root 부터 DFS 탐색을 시작해줍니다.
 자식이 없다면 리프노드이므로 1을 return해주고,
 지워지지않은 자식이 있다면 해당 자식으로 DFS 돌아줍니다.

주의할점은 Root를 지웠을 경우 0을 출력해주는 것입니다.