[백준] 1068번: 트리 (파이썬)

✅문제: 1068번

1068번: 트리

📌개념정리

(1) 트리(Tree)

• 정의: 계층적 관계를 표현하는 비선형 자료구조
• 하나의 루트 노드와 여러 자식 노드들로 구성되며, 노드 간에는 부모-자식 관계가 존재함.
• 트리 구조는 노드와 노드를 연결하는 에지(edge)로 구성되며, 사이클이 존재하지 않음.
• 파이썬에서 트리 사용
  1. 각 노드의 자식 정보를 저장하기 위해 리스트를 사용할 수 있음.
  2. 리스트의 각 요소는 해당 인덱스 노드의 자식 노드 인덱스를 저장하는 또 다른 리스트가 될 수 있음.

📌문제풀이

주어진 트리에서 특정 노드를 삭제한 후, 남은 트리의 리프 노드(자식이 없는 노드)의 수를 세는 문제임. 노드는 0부터 N-1까지의 번호로 주어짐.

1. 입력으로 노드의 수와 트리의 구조, 삭제할 노드의 번호를 받음
2. 트리의 각 노드마다 자식 노드의 인덱스를 저장하는 리스트(children)를 초기화
3. 루트 노드를 찾고, 각 노드의 자식 노드를 리스트에 저장
4. 삭제할 노드와 그 자식 노드를 재귀적으로 탐색하여 모든 연결을 제거
5. 삭제 후의 트리에서 루트 노드부터 시작하여 잎 노드의 수를 재귀적으로 계산

# 노드를 재귀적으로 삭제하는 함수
def delete_node_recursive(node):
    global children
    children[node] = [-1]  # 삭제된 노드의 자식 목록을 [-1]로 설정
    for i in range(len(children)):
        if node in children[i]:
            children[i].remove(node)

# 주어진 노드에서 시작하여 잎 노드의 수를 세는 재귀 함수
def count_leaf_nodes(node):
    if children[node] == [-1]:  # 노드가 삭제된 경우
        return 0
    if not children[node]:  # 자식 노드가 없는 경우, 이 노드는 잎 노드
        return 1
    count = 0  # 잎 노드의 수
    for child in children[node]:
        count += count_leaf_nodes(child)
    return count

n = int(input())  # 노드의 수
tree = list(map(int, input().split()))  # 노드의 부모
delete_node = int(input())  # 삭제할 노드 번호

children = [[] for _ in range(n)]  # 각 노드의 자식 노드 인덱스 저장
root = -1  # 루트 노드 인덱스 초기화

for i in range(n):
    if tree[i] == -1:
        root = i  # 루트 노드
    else:
        children[tree[i]].append(i)

delete_node_recursive(delete_node)

if delete_node == root:
    print(0)
else:
    print(count_leaf_nodes(root))

코드 실행 과정을 설명하면, 예제 입력 1은 5개의 노드가 있고, 노드 간의 관계, 삭제할 노드 번호가 주어짐.

# 예제 입력 1
5
-1 0 0 1 1
2

1) 트리 구조 파악

노드의 부모를 인덱스로 나타낸 배열을 통해 트리를 구성함.

• 인덱스 0: 부모가 -1(루트 노드)
• 인덱스 1, 2: 부모가 0
• 인덱스 3, 4: 부모가 1

2) 초기 트리 구조

    0
   / \
  1   2
 / \
3   4

3) 노드 삭제
노드 2를 삭제함.

    0
   /
  1
 / \
3   4

4) 리프 노드 계산
남은 트리에서 리프 노드를 계산함. 노드 3과 노드 4는 자식이 없으므로 리프 노드임. 따라서 리프 노드의 수인 2를 출력함.

# 예제 출력 1
2

📌후기

• 트리 구조를 파이썬의 리스트를 활용하여 간단하게 표현하는 연습이 필요함.
• 재귀 함수를 사용하여 트리의 노드를 삭제하고 잎 노드의 수를 세는 로직을 구현하는 과정이 어려웠음. 노드 삭제 후에도 올바른 트리 구조를 유지하도록 고려함.

📌참고자료

1) 위키독스, "07. 파이썬으로 트리 구현하기", https://wikidocs.net/193702