문제 설명

트리에서 리프 노드란, 자식의 개수가 0인 노드를 말한다.

트리가 주어졌을 때, 노드 하나를 지울 것이다. 그 때, 남은 트리에서 리프 노드의 개수를 구하는 프로그램을 작성하시오. 노드를 지우면 그 노드와 노드의 모든 자손이 트리에서 제거된다.

입력 조건

첫째 줄에 트리의 노드의 개수 N이 주어진다. N은 50보다 작거나 같은 자연수이다. 둘째 줄에는 0번 노드부터 N-1번 노드까지, 각 노드의 부모가 주어진다. 만약 부모가 없다면 (루트) -1이 주어진다. 셋째 줄에는 지울 노드의 번호가 주어진다.

출력 조건

첫째 줄에 입력으로 주어진 트리에서 입력으로 주어진 노드를 지웠을 때, 리프 노드의 개수를 출력한다.

전체 코드

import sys

sys.setrecursionlimit(10 ** 5)

n = int(sys.stdin.readline().rstrip())
tree_arr = list(map(int, sys.stdin.readline().split()))
target = int(sys.stdin.readline().rstrip())

DELETED = -2


def delete_node_and_child(current: int):
    # 현재 노드 지우기
    tree_arr[current] = DELETED

    for i, elem in enumerate(tree_arr):
        # 현재 노드의 자식을 찾으면, 다음 분기로
        if elem == current:
            delete_node_and_child(i)


delete_node_and_child(target)

answer = 0
for a in range(len(tree_arr)):
    # 지워진 것이 아니고, 트리 배열 내에 부모 노드로 존재하지 않다면 리프노드이다.
    if tree_arr[a] != DELETED and a not in tree_arr:
        answer += 1

print(answer)

딕셔너리로 풀어봤는데, 바로 틀렸다. 다시 풀어볼 때 이유를 분석해봐야겠다.