개발/algorithm
[백준 1068번] 트리 - python
zzi_on2
2022. 4. 29. 23:24
문제 링크
https://www.acmicpc.net/problem/1068
1068번: 트리
첫째 줄에 트리의 노드의 개수 N이 주어진다. N은 50보다 작거나 같은 자연수이다. 둘째 줄에는 0번 노드부터 N-1번 노드까지, 각 노드의 부모가 주어진다. 만약 부모가 없다면 (루트) -1이 주어진다
www.acmicpc.net
풀이
처음엔 부모 노드를 저장해두고
어떠한 노드를 삭제했을 때 해당 노드를 부모로 가지는 노드들도 함께 지운 후,
지워지지 않았고 자기 자신을 부모로 가지는 노드가 없을 때 정답 개수를 증가시켜주는 방식으로 접근
-> 해당 노드보다 더 상위 부모를 삭제했을 때 함께 삭제되어야 하는데 이 경우를 만족시키지 못하므로 재귀적으로 지워나가야 한다.
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)