[백준 1068 파이썬] - 트리

📌 문제

💯 정답

import sys
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 6)

def dfs(d):
    t[d] = -2           # 제거 할 노드 -2 값으로 표시
    for i in range(n):
        if t[i] == d:   # 제거 할 노드를 부모로 갖는 노드들
            dfs(i)      # 재귀적으로 제거


n = int(input())
t = list(map(int, input().split()))
d = int(input())

dfs(d)

cnt = 0
for i in range(n):
    if t[i] != -2 and i not in t:   # t에 i가 있으면 i는 어떤 노드의 부모
        cnt += 1                    # 즉 i는 자식 노드가 있음을 의미함

print(cnt)

📝 설명

• 입력받은 노드들 중 d번째에 있는 d번 노드의 값을 -2로 만든다.
• 또한 값이 d인 노드는 결국 d노드를 부모 노드로 가진다는 의미이므로 이 또한 재귀적으로 -2로 만든다.
• i not in t의 의미는 i가 t에 있으면 결국 i가 어떠한 노드의 부모 노드임을 뜻한다.
• 따라서 리프 노드만을 선택하기 위해서는 값이 -2가 아닌 것과 그때 i가 t에 존재하지 않는 조건을 만족해야 한다.

🙏 참고

👉 [baekjoon] 백준 1068번(파이썬): 트리