[BOJ] 1068번 트리 문제 - Python

www.acmicpc.net/problem/1068

1068번: 트리

 

인접리스트로 단방향 연결을 시킨다.

 

왜냐! 루트부터해서 노드까지로 내려갈꺼니까 다시 올라갈 일은 없다.

 

인접리스트에 연결관계를 넣어주는 과정에서 만약에 삭제될 노드라면 부모와 연결을 시키지 않는다.

 

그렇게만 해두면 알아서 루트타고 내려가다가 부모에서 삭제될 노드로 가지 않게 되고 그 아래에 있는 애들은 탐색될 일이 없을 것이다.

 

탐색은 dfs로 했다.

 

 

def dfs(x):

    global answer

    if not tree[x]:
        answer += 1
        return

    for v in tree[x]:
        dfs(v)

N = int(input())
info = list(map(int, input().split()))
tree = [[] for _ in range(N)]
delete = int(input())

for i in range(N):
    if info[i] == -1:
        root = i
        continue
    if i == delete:
        continue
    tree[info[i]].append(i)


answer = 0
if root != delete:
    dfs(root)
print(answer)