백준) 1068 트리


코드

n = int(input())

li = list(map(int, input().split()))
r = int(input())

tree = [[]for _ in range(n)]
root = 0
ans = 0

for idx, i in enumerate(li):
    if i == -1:
        root = idx
        continue
    if idx == r:
        continue
    tree[i].append(idx)


def dfs(v):
    global ans
    if len(tree[v]) ==0:
        ans += 1
        return
    for i in tree[v]:
        dfs(i)

if root != r:
    dfs(root)
print(ans)


접근방법

  • 트리를 구현한다.
  • 애초에 부모를 주어준다고 명시되어 있기때문에 양방향으로 저장할 필요가 없다.
  • 각 부모별로 자식을 저장하는데 지워야되는 노드는 추가하지 않는다.
  • 그다음 트리를 순회하면서 자식노드가 없는애들일때마다 답을 1씩 증가시켜주면 된다.

챙겨갈점

  • 부모노드를 줄땐 굳이 양방향으로 저장하지 않아도 되고
  • 그러므로 방문한 노드를 저장하는 배열도 필요없을듯.
  • 근데 조건을 좀 잘봐야될듯 싶다.

좋은 웹페이지 즐겨찾기