[BOJ] 1068 - 트리

[문제 설명]

트리 노드의 개수 N이 주어진다.

특정 노드를 지웠을 때, 남은 트리의 Leaf node 수를 구하는 문제

(Leaf node : 자식의 개수가 0개인 노드)

 

(출처 : https://www.acmicpc.net/problem/1068)

1068번: 트리

[조건]

N <= 50

 

[풀이]

트리의 자손 노드를 구하는 문제.

이 문제를 풀 때 문제에 명시되지 않은 조건들을 자의적으로 해석해서는 안된다.

 

<잘못된 가정>

1. 주어지는 트리는 항상 이진 트리이다.

2. root 노드는 항상 인덱스 0이다.

 

그것이 아니라면, 각 노드가 가지고 있는 leaf 노드를 DFS로 구한 후, 삭제하려는 노드의 Leaf 노드의 수를 빼주면 된다.

 

아래와 같이 root 노드에서 탐색을 시작한다.

 

1번 노드는 leaf 노드가 아니기 때문에 3번 자식 노드로 탐색을 들어가고,

3번 노드는 leaf 노드이므로, 다시 1번 노드로 돌아가서, leaf 노드의 개수를 증가시킨다.

 

 

1번 노드의 자식인 4번 노드에서도 동일하게 탐색을 진행한다.

 

 

1번 노드의 모든 자식에 대한 탐색을 마치고,

동일하게 0번 노드에 1번 노드의 결과값을 반영한다.

 

 

0번 노드의 자식인 2번 노드의 탐색을 마찬가지로 진행한다.

 

이렇게 모든 노드의 leaf 노드를 저장해두면, 노드를 삭제한 후에, 전체 leaf 노드의 개수는

기존 0번 노드가 가지고 있던 leaf 노드의 개수에서 삭제하는 노드가 가지고 있는 leaf 노드의 개수를 빼주면 된다.

단 삭제 노드의 부모 노드가 leaf 노드가 될 수 있으므로, 그 경우에는 +1을 더해준다.

 

 

[참고 코드]

https://github.com/b2narae/my-algorithm-notebook/blob/master/src/BOJ/BOJ_1068_DFS_1.java

GitHub - b2narae/my-algorithm-notebook: my-algorithm-notebook