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

import sys
from collections import defaultdict
def input():
    return sys.stdin.readline().rstrip()


def dfs(cur_idx,parent_idx):
    global cnt
    depth[cur_idx] = depth[parent_idx] + 1


    if tree[cur_idx][0] != -1:
        dfs(tree[cur_idx][0],cur_idx)
    cnt += 1
    width[depth[cur_idx]].append(cnt) 
    if tree[cur_idx][1] != -1:
        dfs(tree[cur_idx][1],cur_idx)

N = int(input())
root_check = [0 for _ in range(N+1)]
tree = [[-1 -1] for _ in range(N+1)]
depth = [0 for _ in range(N+1)]
width = defaultdict(list)
for _ in range(N):
    x,left_node,right_node = map(int,input().split())
    tree[x] = [left_node,right_node]
    if left_node != -1:
        root_check[left_node] += 1
    if right_node != -1:
        root_check[right_node] += 1
root_num = -1
for k in range(1,N+1):
    if root_check[k] == 0:
        root_num = k
        break


cnt = 0
dfs(root_num,0)

max_value = 0
max_depth = -1
for d in range(1,max(depth)+1):
    max_width,min_width = max(width[d]),min(width[d])
    if max_value < max_width - min_width + 1:
        max_value = max_width - min_width + 1
        max_depth = d

print(max_depth,max_value)

 

 

이 문제를 풀때 주의할점은 2가지이다.

 

루트노드가 꼭 1인것은 아니다.

 

들어오는 순서가 1,2,3,4,5,6,7,8,....N이 아닐수도 있다.

 

이 2가지를 주의하면 풀면 되는 문제이다.

 

 

먼저 트리를 위한 (N+1)*2의 배열을 만들어뒀다.

 

각 행의 0번인덱스는 왼쪽 자식, 1번인덱스는 오른쪽자식을 의미한다.

 

이 문제는 중위순회를 구현을 해서, 왼쪽 자식->루트->오른쪽자식 순서로 탐색을 해준다.

 

그리고 루트일때 현재의 LEVEL에 width를 저장을 해주엇다.

 

cnt를 0부터 시작했기때문에, append 하기 직전에 +=1 을 해준것이다.

 

만약 1부터 하신분들은 순서를 바꾸면될것이다.

 

그리고 전체 레벨 만큼 탐색을하면서 최대 너비를 구해주면 되는 문제이다.

 

좀 더 깔끔히 하신분들은 level별로 2차원배열을 만든뒤에 둘 중 하나는 최대값 하나는 최소값을 저장을 시켜서 

 

마지막에 바로 계산이 가능하게 한 분들도 계신다.