백준 1068 [트리] 파이썬

https://www.acmicpc.net/problem/1068

1068번: 트리

# 백준 1068
from collections import deque
import sys
input = sys.stdin.readline
N = int(input())
lst = list(map(int, input().split()))
root = 0
del_num = int(input())
tree = [[] for _ in range(N)]
for i in range(N):
    if lst[i] == -1:
        root = i
    else:
        if i != del_num:
            tree[lst[i]].append(i)


def bfs(start, del_num):
    answer = 0
    visited = [0]*(N)
    visited[del_num] = 1
    q = deque([])
    q.append(start)
    while q:
        node = q.popleft()
        if visited[node] == 0 and len(tree[node]) != 0:
            visited[node] = 1
            for next_node in tree[node]:
                if visited[next_node] == 0:
                    q.append(next_node)
        elif visited[node] == 0 and len(tree[node]) == 0:
            answer += 1
    return answer


ans = bfs(root, del_num)
# print(tree)
print(ans)

i) 루트가 0이 아닐수도 있다.

ii) 중간에 노드가 삭제될 수 있다.

를 명심해서 코드를 수정하였다.

 

i) 루트인 경우

visited[root노드번호] =1 을 통해 bfs가 동작하지 않고 바로 탈출 하도록 하였다.

 

ii) 루트가 아닌경우

트리 자체에 연결하지 않음으로써 탐색되지 않도록 하였다.