[DFS/트리] 백준 1068 파이썬 (트리) 골드5

-풀이

import sys

n = int(input())
tree = [[] for _ in range(n)]
p = list(map(int,sys.stdin.readline().split()))
for i in range(n):
    tree[i] = p[i]
remove = int(input())

def delete(remove):
    tree[remove] = -2
    for i in range(n):
        if tree[i] == remove:
            tree[i] = -2
            delete(i)
delete(remove)
cnt = 0
for i in range(n):
    if tree[i] != -2:
        err = 0
        for j in tree:
            if j == i:
                err = 1
                break
        if err == 0:
            cnt += 1
print(cnt)

-풀이설명

트리 문제인데, 제거한 노드에서 가지친 부분까지 제거하기 위해 DFS(깊이우선탐색)를 이용하여 모두 제거해준다. remove에 입력받은 노드 인덱스값을 기준으로 가지친 부분은 DFS를 통해 제거 표시를 해 줄 -2를 각 tree인덱스에 초기화해준다. 그런 뒤 반복문을 차례대로 돌려 -2가 아닌 부분을 찾아내, 그 부분에 대하여 가지친 부분이 있는지 없는지 검사한 후 없을 경우 cnt를 누적하여 값을 출력해준다.

-풀이출처: https://imzzan.tistory.com/40