https://www.acmicpc.net/problem/1068
시간 2초, 메모리 128MB
input :
- N (1 ≤ N ≤ 50)
- 각 노드의 부모 (0 ~ N - 1)
- 지울 노드의 번호
output :
- 리프 노드의 개수를 출력
조건 :
- 주어진 트리에서 입력으로 주어진 노드를 지웠을 떄, 리프 노드의 개수를 찾기.
리프 노드라 함은 자식 노드를 가지고 있지 않은 경우를 뜻한다.
고로 child 딕셔너리를 만들어서 자식 노드의 유무를 체크 하려 했다.
이 때 자식이 없으면 딕셔너리에 키 자체가 없도록 하였다.
Key
노드를 가지게 하고, value로는 자식 노드들의 리스트를 가지게 한다.
예외.
루트 노드를 삭제하는 것을 예외라고 볼 수 있다.
이 경우 start 변수에는 None이 저장되어 있기 때문에 이를 이용해 예외 처리 한다.
import sys
n = int(sys.stdin.readline())
data = list(map(int, sys.stdin.readline().split()))
node = int(sys.stdin.readline())
child = dict()
start = None
for i in range(n):
if i == node:
continue
if data[i] == -1:
start = i
continue
if data[i] not in child:
child[data[i]] = []
child[data[i]].append(i)
if start == None:
print(0)
exit(0)
q, ans = [start], 0
while q:
node = q.pop()
if node not in child:
ans += 1
continue
for next_node in child[node]:
q.append(next_node)
print(ans)
