트리의 높이와 너비 (백준 2250, 파이썬)

inorder(중위 순회)를 사용해야하는 특이한 문제다.

문제에 나와있는 그림을 잘 살펴보면 각 노드에 해당하는 행과 열은 각각 그 노드의 깊이(depth)와 중위순회 순서를 나타내고있기 때문이다.

 

예를 들어 5번 노드는 3행 8열에 위치해 있는데, 이 노드는 깊이가 3, 중위순회 순서 8번에 해당하는 노드이다.

( 중위순회 순서 : 8-4-2-14-9-18-15-5-10-1-16-11-6-12-3-19-17-13-7 )

 

각 노드를 연결하기  위해 node 클래스를 만들어주고, 각 노드의 깊이와 중위순회 순서를 저장하기 위한 변수도 초기화시켜준다. (self.depth, self.order)

 

parent 배열은 각 노드가 부모 노드를 가지고있는지 판별하기 위한 배열인데,

노드를 연결할 때마다 parent 배열에 부모가 있다는 표시를 해주면

이후에 parent가 0인 노드를 찾으면 그게 root 노드가 된다.

 

left, right 배열에 각 깊이에 따른 노드의 열값 최솟값과 최댓값을 저장해둔 후,

right-left+1이 최대인 값을 찾으면 이 트리의 최대 넓이가 된다.

import sys
sys.setrecursionlimit(1000000)
 
class node:
    def __init__(self):
        self.left = -1
        self.right = -1
        self.depth = 0
        self.order = 0
 
def inorder(node, depth):
    global order
    if node == -1:
        return
    inorder(a[node].left, depth+1)
    a[node].depth = depth
    order += 1
    a[node].order = order
    inorder(a[node].right, depth+1)
 
n = int(sys.stdin.readline())
a = [node() for _ in range(10001)]
left = [0]*10001
right = [0]*10001
parent = [0]*10001
order = 0
 
for i in range(n):
    x, b, c = map(int, sys.stdin.readline().split())
    a[x].left = b
    a[x].right = c
    if b != -1:
        parent[b]+=1
    if c != -1:
        parent[c]+=1
 
 
root = 0
for i in range(1, n+1):
    if parent[i] == 0:
        root = i
 
inorder(root, 1)
maxdepth = 0
for i in range(1, n+1):
    depth = a[i].depth
    order = a[i].order
    if left[depth] == 0:
        left[depth] = order
    else:
        left[depth] = min(left[depth], order)
    right[depth] = max(right[depth], order)
    maxdepth = max(maxdepth, depth)
 
maxwidth = 0
anslevel = 0
 
for i in range(1, maxdepth+1):
    if maxwidth < right[i] - left[i] + 1:
        maxwidth = right[i]-left[i]+1
        anslevel = i
 
sys.stdout.write("{} {}".format(anslevel, maxwidth))