1068: 트리

문제 링크

1068: 트리

구현 방식

• 주어진 트리에서 삭제하고자 하는 노드를 삭제한 후에 리프 노드의 개수를 출력하는 문제
• tree는 parent라는 이름의 list를 이용했다
  • index: 자신의 노드, parent[index]: 부모 노드
• dfs를 통해 parent의 값을 'False'로 변경해주어 노드가 지워짐을 표현해주었다
  • parent[node] = "False" -> node를 지움
  • if node == parent[i]: dfs(i) -> 본인을 부모로 하고있는 자식 노드들도 지워줌
• dfs 순회 후 완성된 parent를 통해 1)부모 노드가 있고, 2)본인의 노드가 parent_set에 없다면 리프 노드가 됨을 이용하여 cnt를 구해주었다

코드

import sys

def dfs(node):
    parent[node] = 'False' #지워야하는 노드를 'False'로 변경
    for i in range(N):
        if node == parent[i]: dfs(i) #지워야하는 노드의 자식 노드도 'False'로 변경
    

N = int(sys.stdin.readline()[:-1])
parent = list(map(int, sys.stdin.readline()[:-1].split()))
removed = int(sys.stdin.readline()[:-1])

dfs(removed) #지워야하는 노드들을 'False'로 변경

cnt = 0; parent_set = set(parent)
for i in range(N):
    if parent[i] != 'False' and i not in parent_set: cnt += 1
print(cnt)