[BOJ_9934] 완전 이진 트리 (python)

 

9934번: 완전 이진 트리

 

✅ 문제 설명

 

• 문제를 읽어보면 깊이가 K인 완전 이진 트리가 주어지고, 상근이는 중위순회 방식(왼쪽-> 루트 -> 오른쪽 순)으로 트리를 순회합니다.
• 이런 환경에서 상근이가 방문한 빌딩 번호가 순서대로 주어질 때, 완전 이진트리를 역으로 유추해 각 레벨에 있는 빌딩의 번호를 출력하는 문제입니다.

 

✅ 접근 방식

• 완전 이진 트리라는 점, 상근이가 중위순회를 한다는 것, 그리고 가장 마지막 레벨을 제외한 모든 집은 왼쪽 자식과 오른쪽 자식을 갖는다는 점이 문제의 키 포인트였습니다.

조건1) 중위순회 :
중위순회를 하기 때문에 상근이가 방문한 빌딩의 순서가 (왼쪽노드)->(루트)->(오른쪽노드)로 배치됩니다.

조건2) 완전 이진 트리 & 가장 마지막 레벨을 제외한 노드가 왼쪽 자식과 오른쪽 자식을 갖는다 :
완전 이진 트리는 레벨이 k일때 k-1까지는 포화이진트리이고, 레벨 k부터는 왼쪽부터 노드가 순서대로 채우어진 이진트리입니다. 근데 이때 문제에서 마지막 레벨 k를 제외한 노드가 왼쪽과 오른쪽 자식을 가진다고 하였으므로 사실상 그냥 완전 이진 트리가 아니라 포화 이진 트리가 되게됩니다.

• 따라서 조건1), 조건2) 때문에 상근이의 방문한 빌딩 번호 리스트의 딱 중간이 루트가 됩니다.

✨ 포화 이진 트리? 완전 이진 트리? ✨

포화이진트리(왼)와 완전이진트리(오)

포화 이진 트리는 이진트리이면서 서브트리까지 모두 빈 곳이 없이 꽉찬 트리입니다.

완전 이진 트리는 마지막 레벨이 k라면 k-1레벨까지는 포화 이진 트리이지만, 마지막 레벨 k에서는 왼쪽부터 노드가 순서대로 채워진 이진트리입니다. 따라서 마지막 레벨이 다 차있어도 되고, 안 차 있어도 됩니다. 

 

참고한 사이트: 포화이진트리, 완전이진트리 차이는 뭘까?

 

✅ 코드 설명

import sys

k = int(sys.stdin.readline())
arr = list(map(int, sys.stdin.readline().split()))
levels = [[] for _ in range(k)]

• 우선 트리 레벨값 k, 상근이가 다녀온 건물의 번호를 순차적으로 적은 배열 arr의 값을 입력받아줍니다.
• 그리고 levels라는 트리의 레벨별로 노드를 저장하기 위한 이중 리스트를 선언해줍니다.

 

def separation(arr, depth):
    if len(arr) == 1:  # 요소가 하나밖에 없을 때
        levels[depth].extend(arr)
        return

    mid = len(arr) // 2
    levels[depth].append(arr[mid])  # 중간값=루트만 depth 레벨이므로 levels[depth]에 넣어줌
    separation(arr[:mid], depth + 1)
    separation(arr[mid + 1:], depth + 1)

• 가장 중요한 separation 함수입니다. 인자값으로 배열과 깊이가 주어집니다.
• 요소가 하나 밖에 없을 땐 루트를 뽑을 필요없이 그냥 그 요소가 루트에 해당하는 값이 되므로 입력으로 들어온 depth 깊이에 값을 넣어줍니다.
• 요소가 하나 이상일때는 뭐가 루트값인지 판별해야합니다. 앞에서 설명했듯이 조건1), 조건2) 때문에 상근이의 방문한 빌딩 번호 리스트의 딱 중간이 루트가 되므로 중간값을 depth 깊이에 값으로 넣어줍니다.
• 이후 루트가 아닌 남은 값인 왼쪽 자식노드, 오른쪽 자식노드에 대해서도 separation 함수를 수행하여 depth+1에 해당하는 루트노드들을 판별하여 해당 레벨에 값을 넣어줍니다. 

 

separation(arr, 0)

for level in levels:
    for i in level:
        print(i, end=" ")
    print()

• levels 배열을 만들때 인덱스 0번부터 k-1까지를 사용했으므로 separation을 할때 depth의 초기값을 0으로 줍니다.
• 이후 각 레벨별 노드를 출력해줍니다. separation(arr[:mid], depth + 1) ->  separation(arr[mid + 1:], depth + 1) 순으로 호출했기 때문에 출력은 왼쪽에서부터 오른쪽 순서대로 출력이 됩니다.

 

✅ 최종 코드

# 완전 이진 트리

import sys

k = int(sys.stdin.readline())
arr = list(map(int, sys.stdin.readline().split()))
levels = [[] for _ in range(k)]


def separation(arr, depth):
    if len(arr) == 1:  # 요소가 하나밖에 없을 때
        levels[depth].extend(arr)
        return

    mid = len(arr) // 2
    levels[depth].append(arr[mid])  # 중간값=루트만 depth 레벨이므로 levels[depth]에 넣어줌
    separation(arr[:mid], depth + 1)
    separation(arr[mid + 1:], depth + 1)


separation(arr, 0)

for level in levels:
    for i in level:
        print(i, end=" ")
    print()

 

❇️ 코멘트

• 배열의 중간에 있는 값에 접근할 때는 mid = len(arr)//2로 두고, arr[mid]로 접근하면 된다는걸 알게되었습니다.
• extend 함수 = extend는 리스트를 리스트안으로 넣을 때 리스트의 원소를 꺼내서 넣어줍니다.
• 접근 방식을 파악해도 구현이 생각보다 쉽지 않은 문제였습니다. -> level값을 인자로 주면서 재귀를 이용하여 푸는 방법을 생각할 줄 알아야 했습니다.