백준 1068 트리 / python

문제 :

풀이 point

트리를 구성한 후 깊이 탐색을 활용하여 문제를 해결할 수 있다.

인접리스트를 활용하여 루트를 제외한 나머지 노드들의 트리를 구성하고, 지우려는 노드는 부모 단에서 제거한다. (부모의 자식 노드에서 지우려는 노드를 탐색후 삭제) 부모에서 제거하면 밑으로 절대 내려갈 수 없기 때문에 굳이 지우지 않아도 알아서 탐색이 되지 않는다.

풀이 코드

N = int(input())
nodes = list(map(int, input().split()))
rNode = int(input())

graph = [[] for _ in range(N)]

cnt = 0

for i in range(N):
  if nodes[i] == -1:
    root = i
  else: graph[nodes[i]].append(i)

if rNode == root:
  print(0)
  exit()

parent = nodes[rNode]
graph[parent].remove(rNode)

def dfs(node):
  global cnt

  if len(graph[node]) == 0:
    cnt += 1
    return
  
  for n in graph[node]:
    dfs(n)

dfs(root)
print(cnt)