[BOJ 1068] 트리
- 문제풀이
본문
트리에서 리프 노드란, 자식의 개수가 0인 노드를 말한다.
트리가 주어졌을 때, 노드 하나를 지울 것이다. 그 때, 남은 트리에서 리프 노드의 개수를 구하는 프로그램을 작성하시오. 노드를 지우면 그 노드와 노드의 모든 자손이 트리에서 제거된다.
예를 들어, 다음과 같은 트리가 있다고 하자.
현재 리프 노드의 개수는 3개이다. (초록색 색칠된 노드) 이때, 1번을 지우면, 다음과 같이 변한다. 검정색으로 색칠된 노드가 트리에서 제거된 노드이다.
이제 리프 노드의 개수는 1개이다.
입력
첫째 줄에 트리의 노드의 개수 N이 주어진다. N은 50보다 작거나 같은 자연수이다. 둘째 줄에는 0번 노드부터 N-1번 노드까지, 각 노드의 부모가 주어진다. 만약 부모가 없다면 (루트) -1이 주어진다. 셋째 줄에는 지울 노드의 번호가 주어진다.
출력
첫째 줄에 입력으로 주어진 트리에서 입력으로 주어진 노드를 지웠을 때, 리프 노드의 개수를 출력한다.
제한
| 시간 제한 | 메모리 제한 |
|---|---|
| 2sec | 128MB |
풀이
풀이 방법은 여러 가지가 있을 수 있다. 노드의 개수가 50개로 매우 적은 편이고, 시간은 2초로 매우 널널한 편이라서, 정답을 찾아갈 수 있는 알고리즘도 크게 제약을 받지 않는다. 물론, 매우 비효율적으로 움직여도 가능하다.
입력으로 주어지는 정보는 노드의 자식들이 아닌 부모이므로, 루트부터 시작하여 트리를 만들어나가기는 쉽지 않다. 그래서, 트리 구조를 만들지 않고 답을 찾는 방법을 생각해보려했다. 모든 노드들의 부모 정보를 가지고 있으므로, 이를 이용하여 특정 노드가 리프 노드인지 확인하면 된다.
문제에서 원하는 조건인 “리프 노드”의 경우, 자식 노드가 0개인 노드를 의미한다. 즉, 어떤 노드 $x$에 대해 모든 노드가 $x$를 부모로 가지지 않을 때, 우리는 $x$를 리프 노드라고 할 수 있다. 이를 이용하여, 모든 노드에 대해서, 다른 모든 노드의 부모가 자신이 아닐 때, 그것을 리프 노드로 지정할 수 있다. 시간복잡도는 노드의 개수 $n$에 대해 $O(n^2)$.
다만, 문제에서는 삭제할 노드가 하나 존재한다. 노드 하나를 삭제하면 그 아래의 모든 노드가 삭제된다. 다행히도, 위와 같은 방법을 사용할 것이라면, 삭제되는 노드는 아예 없는 셈 치고 하던대로 진행하면 된다. 그 아래의 노드들의 경우, 삭제되는 노드가 이미 없는 상황이라면 그 아래를 탐색하지는 않으므로 고려 대상이 아니기 때문이다. 즉, 루트부터 트리 탐색을 진행하며, 삭제되는 노드인 경우는 탐색하지 않고, 리프 노드의 개수를 세면 되는 쉬운 문제이다. DFS 탐색과 BFS 탐색 모두 구현할 수 있으나, 구현을 쉽게 하기 위해 DFS 방법을 선택하여 구현하였다.
소스코드
Github Link : Source Code
참고 알고리즘 : DFS 탐색