[ 2250 ] [ Tree ] 트리의 높이와 너비

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

2250번: 트리의 높이와 너비

 

---

풀이 과정

---

1. 루트 노드가 무조건 1번인건 아니기 때문에 루트 노드의 번호를 구한다.
   1. 1번부터 N번까지 노드를 Set에 저장시켜 둔 다음, 입력되는 노드의 오른쪽 자식이거나 왼쪽 자식인 경우, Set에서 빼준다.
   2. Set에 노드가 한개 남게 되면, 그게 루트 노드이다. 
2. 각각의 노드가 위치하는 열을 구한다. 
   
   1. 그 전에, 각각의 노드의 자식 노드 수를 구해준다.
   2. 현재 노드의 위치는 범위가 (left, right)일 때, left + 왼쪽 자식 노드 수 + 1이라고 볼 수 있다.
   3. 현재 노드의 위치를 구해준 다음, 왼쪽 자식 노드에 대해서는 (left, 현재 노드의 위치 - 1), 오른쪽 자식 노드에 대해서는 (현재 노드의 위치+1, right) 범위만큼 recursion으로 진행한다.
3. 열을 구해준다면, 이제 루트 노드에서 시작해서 BFS를 진행한다.
   1. 각각의 레벨에 열 정보들을 모두 저장시켜 둔다.
4. 저장해둔 레벨별 열 정보들을 오름차순으로 정렬시켜 준다.
   1. 맨 마지막 인덱스가 최댓값, 맨 앞 인덱스가 최솟값이므로 최댓값 - 최솟값을 구해준다.
   2. 최댓값-최솟값이 현재 정답보다 크다면, 현재 정답과 인덱스를 저장시켜 둔다.

---

소스 코드

---

import sys
from collections import deque


input = lambda: sys.stdin.readline().rstrip()
N = int(input())
left_child = [-1] * (N+1)
right_child = [-1] * (N+1)
p = set([i for i in range(1, N+1)])

for i in range(N):
    a, b, c = map(int, input().split())
    left_child[a] = b
    right_child[a] = c
    if b in p:
        p.remove(b)
    if c in p:
        p.remove(c)

root_node = list(p)[0]
child_count = [-1] * (N+1)
pos = [0] * (N+1)

def get_chk_child(p):
    count = 0
    if left_child[p] != -1:
        count += get_chk_child(left_child[p])
    if right_child[p] != -1:
        count += get_chk_child(right_child[p])
    child_count[p] = count + 1
    return count + 1

def allow_number(p, left, right):
    pos[p] = left

    if left == right:
        pos[p] = left
        return
    
    if left_child[p] != -1:
        pos[p] = left+child_count[left_child[p]]

    if left_child[p] != -1:
        allow_number(left_child[p], left, pos[p]-1)

    if right_child[p] != -1:
        allow_number(right_child[p], pos[p]+1, right)

get_chk_child(root_node)
allow_number(root_node, 1, N)
step = [[] for _ in range(10001)]
queue = deque([[root_node, 0]])
while queue:
    nx, s = queue.popleft()
    step[s].append(pos[nx])
    if left_child[nx] != -1:
        queue.append([left_child[nx], s+1])
    if right_child[nx] != -1:
        queue.append([right_child[nx], s+1])

level = 1
answer = 1
for i in range(10001):
    step[i].sort()
    if len(step[i]) > 1:
        if answer < step[i][-1] - step[i][0] + 1:
            answer = step[i][-1] - step[i][0] + 1
            level = i+1

print(level, answer)