트리 ( 1068 번 )

1068번: 트리

 

---

🧠 알고리즘

• 트리 탐색 (BFS 활용) + 조건 체크

 

 

✔️ 동작 방식

• 입력으로 부모 배열을 받아 트리 구조를 딕셔너리(conn_dict)로 변환
• 지울 노드(rm_node)가 루트라면 리프 노드가 없으므로 0 반환
• 자식이 없거나 모두 지워진 경우 → 리프 노드로 카운트
• 모든 노드를 탐색한 후 리프 노드 개수를 반환

---

 

🧾 코드

import sys
from collections import deque

def _mk(n):
    root_node, answer = 0, {i: [] for i in range(n)}
    n_list = list(map(int, sys.stdin.readline().rstrip().split()))

    for idx in range(len(n_list)):
        if n_list[idx] == -1:
            root_node = idx
            continue

        answer[n_list[idx]].append(idx)

    return root_node, answer


def _main(n):
    answer = 0
    root_node, conn_dict = _mk(n)
    rm_node = int(sys.stdin.readline().rstrip())

    # 선제 조건
    if rm_node == root_node:
        return 0
    
    conn_dict.pop(rm_node)
    queue = deque([root_node])
    visit_check = [False] * n
    visit_check[root_node] = True
    
    while queue:
        now_node = queue.popleft()

        check = False  
        for next_node in conn_dict[now_node]:
            if next_node in conn_dict and visit_check[next_node] is False: # 방문 안한 노드
                visit_check[next_node] = True
                check = True
                queue.append(next_node)
                
        if check is False: # 리프 노드
            answer += 1
        
    return answer

n = int(sys.stdin.readline().rstrip())
print(_main(n))

---

 

⏱️ 시간 복잡도

while queue : 루트 부터 그래프를 탐색하며 리프 노드 카운트 ( 선형 시간 복잡도 )
	for next_node in conn_dict[now_node]:
    
해당 알고리즘 시간 복잡도 :  선형 시간 복잡도 ( O(n) )