[BOJ] 1068번 트리(리프노드 개수 구하기)

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

[ 문제 요약 ] 

- 입력으로 트리의 노드 개수, 각 노드의 부모 개수, 삭제 될 노드가 주어집니다.

- 이 경우에서 리프 노드의 개수를 구하는 문제 입니다.

[ 풀이 과정 ] 

- 예외의 경우를 많이 따져보고 그에 따른 조건문을 끊임없이 생각한 문제입니다.

- 트리에 대한 정확한 개념을 필요로 합니다. (아래는 문제를 풀면서 생각해야 할 선행지식 입니다.)

* 선행 지식 *

- 리프노드란? 단말노드라고도 불리며, 자식 노드가 없는 노드를 말합니다.

  (예를 들어, 0이라는 하나의 노드만 있는 경우엔 0은 리프노드입니다.)

- 이 문제에서는 포레스트(트리들의 집합)의 경우를 고려해 주어야 합니다.

  (즉, 루트노드가 여러개 인 경우를 고려해주어야 합니다.

   예를 들어, 0 , 1, 2 모두 루트 노드 일 수 있고, 이 때의 리프노드 개수는 3입니다.)

 

[ 소스 코드 ]

- 주석으로 코드(변수)에 대한 설명을 붙여놨습니다!!

- 트리의 연결 관계를 표현하기 위해 vector를 사용하였고, 저는 삭제되는 노드를 굳이 삭제하지 않고, 루트노드에서부터 검사를 하면서 삭제된 노드를 만나게 되는 경우에 count를 하지 않는 방향으로 구현하였습니다.