boj2250 트리의 높이와 너비

난이도 골드2

 

문제

이진트리를 다음의 규칙에 따라 행과 열에 번호가 붙어있는 격자 모양의 틀 속에 그리려고 한다. 이때 다음의 규칙에 따라 그리려고 한다.

1. 이진트리에서 같은 레벨(level)에 있는 노드는 같은 행에 위치한다.
2. 한 열에는 한 노드만 존재한다.
3. 임의의 노드의 왼쪽 부트리(left subtree)에 있는 노드들은 해당 노드보다 왼쪽의 열에 위치하고, 오른쪽 부트리(right subtree)에 있는 노드들은 해당 노드보다 오른쪽의 열에 위치한다.
4. 노드가 배치된 가장 왼쪽 열과 오른쪽 열 사이엔 아무 노드도 없이 비어있는 열은 없다.

이와 같은 규칙에 따라 이진트리를 그릴 때 각 레벨의 너비는 그 레벨에 할당된 노드 중 가장 오른쪽에 위치한 노드의 열 번호에서 가장 왼쪽에 위치한 노드의 열 번호를 뺀 값 더하기 1로 정의한다. 트리의 레벨은 가장 위쪽에 있는 루트 노드가 1이고 아래로 1씩 증가한다.

아래 그림은 어떤 이진트리를 위의 규칙에 따라 그려 본 것이다. 첫 번째 레벨의 너비는 1, 두 번째 레벨의 너비는 13, 3번째, 4번째 레벨의 너비는 각각 18이고, 5번째 레벨의 너비는 13이며, 그리고 6번째 레벨의 너비는 12이다.

우리는 주어진 이진트리를 위의 규칙에 따라 그릴 때에 너비가 가장 넓은 레벨과 그 레벨의 너비를 계산하려고 한다. 위의 그림의 예에서 너비가 가장 넓은 레벨은 3번째와 4번째로 그 너비는 18이다. 너비가 가장 넓은 레벨이 두 개 이상 있을 때는 번호가 작은 레벨을 답으로 한다. 그러므로 이 예에 대한 답은 레벨은 3이고, 너비는 18이다.

임의의 이진트리가 입력으로 주어질 때 너비가 가장 넓은 레벨과 그 레벨의 너비를 출력하는 프로그램을 작성하시오

입력

첫째 줄에 노드의 개수를 나타내는 정수 N(1 ≤ N ≤ 10,000)이 주어진다. 다음 N개의 줄에는 각 줄마다 노드 번호와 해당 노드의 왼쪽 자식 노드와 오른쪽 자식 노드의 번호가 순서대로 주어진다. 노드들의 번호는 1부터 N까지이며, 자식이 없는 경우에는 자식 노드의 번호에 -1이 주어진다.

출력

첫째 줄에 너비가 가장 넓은 레벨과 그 레벨의 너비를 순서대로 출력한다. 너비가 가장 넓은 레벨이 두 개 이상 있을 때에는 번호가 작은 레벨을 출력한다.

 

 

 

---

내 풀이 https://github.com/yj0903/python_CodingTest/blob/main/DataStructure/tree/boj2250.py

 

문제를 보자마자 inorder traversal 형태임을 알아차리는게 중요한거 같다.

기존에 inorder traversal 형태 문제에서 조금 더 구현해야하는 부분이 추가된 문제다.

1.  테스트케이스가 노드를 순서대로 넣어주지 않는 듯함. 따라서 어떤  노드가 root인지 확인하는 parent 추가됨. 

2. 다른 사람들 코드를 보면 레벨값을 노드에 넣어서 작성했는데, 나는 순회하면서 level_list 배열 하나 만들어서 저장했음. 이유는.. 그렇게 저장하면 배열의 인덱스 차이가 곧 너비여서, 인덱스 연산만 하면 되니까 시간복잡도(?) 측면에서 좋을거라는 생각으로 그렇게 구현함..

 

# boj2250 트리의 높이와 너비 (골드2)
import sys

class Node:
    def __init__(self, data, left_node, right_node):
        self.parent = -1
        self.data = data
        self.left_node = left_node
        self.right_node = right_node

# 중위 순위 함수 생성. level_list 유의
def inorder(level, node):
    global level_list
    # left
    if node.left_node != -1:
        inorder(level + 1, tree[node.left_node])
    # middle
    level_list.append(level) # 출력 되는 값의 레벨을 순서대로 배열에 담는다
    # right
    if node.right_node != -1:
        inorder(level + 1, tree[node.right_node])
    return level_list

# 변수 선언
number = int(input())
tree = {}
root = -1
level_list = list()  # 전역변수 선언, 각각의 레벨이 담길 리스트

# 트리 초기화(선언이 되어 있어야 아래 parent에 값대입 가능함..)
for i in range(1, number + 1):
    tree[i] = Node(i, -1, -1)

# 입력받아 트리에 넣기, parent 유의 (parent가 -1이면 루트)
for i in range(number):
    data, left_node, right_node = list(map(int, sys.stdin.readline().split()))
    tree[data].left_node = left_node
    tree[data].right_node = right_node
    if left_node != -1:
        tree[left_node].parent = data
    if right_node != -1:
        tree[right_node].parent = data
# 트리에 root 노드 반환
for i in range(1, number + 1):
    if tree[i].parent == -1:
        root = i

result = inorder(1, tree[root])
result_reverse = list(reversed(result))
max_width = 0
level_val = 0

# 앞에서 찾고, reverse해서 뒤에서 찾기
for i in range(1, max(result) + 1):
    min_val = result.index(i)
    max_val = len(result) - result_reverse.index(i)

    width = max_val - min_val
    if max_width < width:
        max_width = width
        level_val = i

# 결과 출력
print(level_val, max_width)

 

어렵다 골드.. 

마지막 제출한 두 개는 입력을 할 때 어떻게 했는가에 따라 시간이 달라졌다.

즉, 시간복잡도 측면에서 확실히 input() 보다는 stdio.readline()이 훨훨씬 좋다는 것!