알고리즘 - Python / 백준 - 1068번 : 트리

1068번: 트리 (acmicpc.net)

1068번: 트리

 

---

풀이

• 트리를 입력받고 하나의 노드를 지웠을 때 , 트리의 리프노드의 개수를 구하는 문제이다.
• 문제에서 부모 노드가 없는 경우를 -1 로 두고 있으므로 , -1 인 경우를 모두 루트 노드로 둔다.
• 이후 해당 트리를 탐색하며 자식 노드가 없을 경우 정답에 1씩 더해 최종 리프노드 숫자를 출력하면 된다.

 

import sys
n = int(sys.stdin.readline())
stack = list(map(int, sys.stdin.readline().split(" ")))
edge = [[-1] for _ in range(n)]
k = int(sys.stdin.readline())
root = []
for i in range(0,n):
    if stack[i] >= 0 and i != k:
        edge[stack[i]].append(i)
    elif stack[i] == -1 and i != k:
        root.append(i)
edge[k] = [-1]
ans = 0

visited = [0]*n
while root:
    n = root.pop()
    if visited[n] == 0:
        visited[n] = 1
        if len(edge[n]) == 1:
            ans += 1
        else:
            sub = edge[n]
            sub.pop(0)
            for i in sub:
                root.append(i)
print(ans)

---