[백준]1068번 트리 - ptyhon파이썬

문제

 

 

이 문제를 보면 dfs로 풀어야한다는 감이 온다 왜냐하면 삭제해야하는 노드의 끝까지 방문해서 차례대로 삭제를 해주어야 하기 때문이다.

 

이때 삭제를 실제로 하게 되면은 인덱스 번호를 수정해야 해서 복잡해지므로 삭제를 해야할 노드의 값을 변경해주는 방식으로 업데이트를 해주었다.

 

실제 코드

from collections import deque
n = int(input())
nodes = list(map(int, input().split()))
d = int(input())

def dfs(d):
    nodes[d] = -10
    for i in range(n):
        #d번 노드를 부모로 가진 자식노드 재귀통해 삭제
        if d == nodes[i]:
            
            dfs(i)
            

dfs(d)
ans =0 
for i in range(n):
    #-10은 제거된노드를 의미, nodes에 없다는 건 자식노드를 가지지 않는다는걸 의미
    if nodes[i] != -10 and i not in nodes:
        ans+=1

print(ans)

 

 

dfs로 푸는 거라는 감은 쉽게 왔는데 문제를 해결하는 방법이 쉽게 생각이 안났던 문제였다.... dfs를 많이 연습해봐야 할 것 같다