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

문제

 

풀이

입력받은 정보를 바탕으로 각 노드의 자식 노드를 저장하는 child 배열을 만들었다.

삭제할 노드의 경우 child 배열에 추가하지 않았다.

n = int(input())
parent = list(map(int, input().split()))
delNode = int(input())

child = [[] for _ in range(n)]

for idx in range(n):
    if parent[idx] == -1 or idx == delNode:
        continue
    child[parent[idx]].append(idx)

 

자식 노드가 없다는 것은 리프 노드임을 의미

제거할 노드의 자식 노드들을 전부 리프 노드를 만들기 위해 해당 노드에 -1 대입

def dfs(d):
    # 리프 노드인 경우
    if child[d] == []:
        child[d].append(-1)
        return
    # 리프 노드가 아닌 경우
    for c in child[d]:
        dfs(c)

코드

import sys
input = sys.stdin.readline

n = int(input())
parent = list(map(int, input().split()))
delNode = int(input())

child = [[] for _ in range(n)]

for idx in range(n):
    if parent[idx] == -1 or idx == delNode:
        continue
    child[parent[idx]].append(idx)
    
def dfs(d):
    # 리프 노드인 경우
    if child[d] == []:
        child[d].append(-1)
        return
    # 리프 노드가 아닌 경우
    for c in child[d]:
        dfs(c)

dfs(delNode)

ans = 0
for i in range(n):
    if child[i] == []:
        ans += 1

print(ans)

 

마무리

트리의 특징을 잘 알아야 풀 수 있는 문제