[Python/파이썬] 백준 1068 - 트리

문제 설명

입력과 출력

 

입출력 예제

# 입력
5
-1 0 0 1 1
2

# 출력
2

---

풀이 코드

 

정답 코드

import sys
input = sys.stdin.readline

n = int(input())
tree = list(map(int, input().split())) 
delete = int(input())

def dfs(del_node):
    tree[del_node] = -10 # 의미없는 숫자를 부여해 제거함을 의미
    for i in range(n):
        if del_node == tree[i]: # tree[i]가 del_node의 자식이면 재귀를 통해 삭제
            dfs(i)
dfs(delete)
cnt = 0
for i in range(n):
    if tree[i] != -10 and i not in tree: # 제거된 노드가 아니고 i의 자식이 없다면
        cnt += 1

print(cnt)

 

예제에 해당하는 대로 트리를 그려보면 다음과 같습니다.

2번을 제거 했을 때 더 이상 자식이 없는 리프노드는 3번, 4번 노드로 정답은 2

부가적인 설명은 주석에 달아 놓아 위 그림을 참고하여 코드를 작성해본다면 쉽게 이해가 될 겁니다.