[백준 1068번] 트리 - python

문제 링크

https://www.acmicpc.net/problem/1068

1068번: 트리

풀이 

처음엔 부모 노드를 저장해두고

어떠한 노드를 삭제했을 때 해당 노드를 부모로 가지는 노드들도 함께 지운 후,

지워지지 않았고 자기 자신을 부모로 가지는 노드가 없을 때 정답 개수를 증가시켜주는 방식으로 접근 

-> 해당 노드보다 더 상위 부모를 삭제했을 때 함께 삭제되어야 하는데 이 경우를 만족시키지 못하므로 재귀적으로 지워나가야 한다. 

 

def delete(node):
    # 지워진 함수는 -2로 표시 
    parent[node] = -2
    for i in range(n):
    	# 지운 노드를 부모로 가지는 노드들도 함께 재귀적으로 삭제해주기 
        if parent[i] == node :
            delete(i)

n = int(input())

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

node = int(input())

delete(node)
ans = 0 
for i in range(n):
	# 지워지지 않았고 자신을 부모로 가지는 노드들이 없으면 
    if parent[i] != -2 and i not in parent :
        ans += 1 
        
print(ans)