첫째 줄에 노드의 개수 입력
둘째 줄에 각 노드의 부모 노드의 정보 입력
셋째 줄에 제거할 노드 정보 입력
셋째 줄에 입력받은 노드를 제거했을 경우 리프 노드의 개수를 출력
한 노드를 제거했을 경우 그 밑의 자식 노드들을 제거하여 남은 노드 수를 출력하는 풀이 방법
제거된 노드의 data 값을 -2로 설정하고 최종적으로 노드의 data != -2 & 자식 노드의 개수 == 0 인 조건을 만족하는 노드를 체크
깊이 우선 탐색(dfs)를 사용하여 풀이
tree = [Node(idx) for idx in range(N)]
for idx in range(N):
parent = info[idx]
tree[idx].parent = parent
if parent != -1: tree[parent].child.append(idx)
dq = deque([target])
while dq:
node = dq.pop()
if tree[node].data == -2: continue
else:
if not tree[node].parent == -1:
parent = tree[node].parent
child_idx = tree[parent].child.index(node)
tree[parent].child.pop(child_idx)
tree[node].data = -2
for child in tree[node].child: dq.append(child)
for idx in range(N):
if tree[idx].data != -2 and len(tree[idx].child) == 0: ans += 1