[python] 백준 2250 트리의 높이와 너비

https://www.acmicpc.net/problem/2250

2250번: 트리의 높이와 너비

 

문제해결

중위 순회 트리

중위 순회(incoder)(왼쪽 하위트리 → 루트 → 오른쪽 하위 트리 방향) 방식으로 보며 되며 그 순서를 x축에 표현한 것으로서 num이라는 변수로 표현하였으며 그 때의 깊이(level)을 index로 하여 row리스트에 저장을 한다.(append)

row리스트에 모든 로드를 저장한 후 level=1부터 level=n까지 각 레벨에서 최대 x축(num)값을 가진 노드의 num값과 최소 x축(num)값을 가진 노드의 너비를 계산하여 그중에서 최댓값이 나오는 level과 그 최댓값을 출력하면 된다.

 

CODE

import sys
input = sys.stdin.readline

n = int(input()) # 노드의 개수
s = [[0]*2 for _ in range(n+1)] # s[k][0] k 노드에 들어있는 왼쪽 자식, s[k][1]은 k노드에 들어있는 오른쪽 자식
node = [0 for _ in range(n+1)] # node[k]가 몇단계 깊이에 있는지
row = [[] for _ in range(n+1)] # row[k]는 k깊이에 있는 x축 숫자들을 모아놓은 집합이다. 
num = 1

def inorder(root,level):
    global num
    if s[root][0] != -1: 
        inorder(s[root][0], level+1)
    row[level].append(num)
    num +=1
    if s[root][1] != -1:
        inorder(s[root][1], level+1)
for i in range(n):
    ro, le, ri = map(int, input().split()) #부모, 왼쪽자식, 오른쪽자식
    s[ro][0] = le
    s[ro][1] = ri
    node[ro] +=1
    if le != -1: # 왼쪽 자식이 있으면
        node[le] +=1
    if ri != -1: # 오른쪽 자식이 있으면
        node[ri] +=1
for i in range(1,n+1):
    if node[i] == 1: # 깊이 1단계부터 시작 참고로 1단계는 한개의 수 밖에 없음
        root = i # root는 가장 꼭대기에 있는 노드를 말하며 i가 가장 꼭대기에 있는 노드이다.(보통 1이 나오기는 함)
        inorder(root,1) # 꼭대기 점부터 inorder 시작!
result = max(row[1]) - min(row[1])+1 #level1의 너비계산
level = 1
for i in range(2,n+1):
    if row[i]:
        if result < max(row[i]) - min(row[i]) + 1:
            result = max(row[i]) - min(row[i]) + 1
            level = i
print(level, result)