[BOJ] #2250 - 트리의 높이와 너비

2250번: 트리의 높이와 너비

 

 

** 문제 유형

• 트리, 구현

 

** 풀이

1. 중위 순회를 이용하면 x축을 기준으로 왼쪽부터 방문한다는 특징이 있음
2. 중위 순회 알고리즘을 이용하고, 추가적으로 level 값을 저장하도록 하여 문제 해결 가능

 

 

 

class Node:
    def __init__(self, number, left_node, right_node):
        self.parent = -1 # 부모가 존재하는지 확인, 없으면 루트
        self.number = number
        self.left_node = left_node
        self.right_node = right_node

---

def in_order(node, level):
    global level_depth, x

    level_depth = max(level_depth, level)

    if node.left_node != -1:
        in_order(tree[node.left_node], level + 1)

    level_min[level] = min(level_min[level], x)
    level_max[level] = max(level_max[level], x)
    x += 1

    if node.right_node != -1:
        in_order(tree[node.right_node], level + 1)

---

n = int(input())

tree = {}
level_min = [n] # 각 level에서의 최소값 기록
level_max = [0] # 각 level에서의 최대값 기록
root = -1 # 루트 노드 인덱스
x = 1 # 트리의 너비 증가 기록
level_depth = 1

for i in range(1, n + 1):
    tree[i] = Node(i, -1, -1) # 자식이 없다고 초기화
    level_min.append(n)
    level_max.append(0)

for _ in range(n):
    number, left_node, right_node = map(int, input().split())

    tree[number].left_node = left_node
    tree[number].right_node = right_node

    if left_node != -1:
        tree[left_node].parent = number
    if right_node != -1:
        tree[right_node].parent = number

for i in range(1, n + 1):
    if tree[i].parent == -1:
        root = i # 부모가 없는 노드가 루트

in_order(tree[root], 1) # 루트에서부터 중위 순회

result_level = 1
result_width = level_max[1] - level_min[1] + 1

for i in range(2, level_depth + 1):
    width = level_max[i] - level_min[i] + 1

    if result_width < width: # 너비가 가장 넓을 때의 level 값 기록
        result_level = i
        result_width = width

print(result_level, result_width)