백준 1068 트리 파이썬 풀이

정답 코드

# BOJ 1068 트리
# 2022 06 23 08:39 - 09:12
 
import sys
input = sys.stdin.readline
 
def main():
    v = int(input())
    graph = [[] for _ in range(v) ]
 
    connection = list(map(int,input().split()))
 
    root = -2
    for idx, value in enumerate(connection):
        if value == -1:
            root = idx
        else:
            graph[value].append(idx)
    deleteNode = int(input())
 
    if deleteNode == root :
        print(0)
        return 
    # print(graph)
 
    parentNode = connection[deleteNode]
 
    graph[parentNode].remove(deleteNode)
    graph[deleteNode]=[]
 
    # print(graph)
 
    leaf = 0
    def dfs(cur):
        nonlocal leaf
        for next in graph[cur]:
            if graph[next]:
                dfs(next)
            else:
                leaf+=1
        return
 
    if not graph[root]:
        print(1)
        return
    dfs(root)
    print(leaf)
# [[2], [], [], [], []]
# [[1], [3, 4], [], [], []]
 
main()

핵심 풀이

1. 노드를 삭제 할 때, 부모에서 한 번, 자식노드 삭제 총 두 번 해줘야 한다.
2. 방문배열을 따로 만들 필요가 없다.
3. 루트를 삭제할 경우와, 하나뿐인 루트의 자식을 삭제할 경우 예외처리를 해줘야 한다.