[백준] 2250번(트리의 높이와 너비)

백준 2250번

최종 제출 코드

import sys
from collections import deque
input = sys.stdin.readline

# 입력받기
# 부모와 자식 관계를 정의하며 root 노드를 구함
# 어떤 노드의 자식으로도 나타나지 않는 노드가 root 노드임
n = int(input().rstrip())
array = dict()
root = [False] + [True]*n

for i in range(n):
  parent, left, right = map(int, input().split())
  array[parent] = [left, right]

  if left != -1:
    root[left] = False
  if right != -1:
    root[right] = False

# 루트 노드가 누구인지 구하기
root_node = root.index(True)

# 트리를 중위순환하면서 각 노드들의 좌표구하기
width = dict()
cnt = 1

def inorder(parent):

  global cnt
  
  left = array[parent][0]
  right = array[parent][1]
  
  if left != -1: inorder(left)
  width[parent] = cnt
  cnt += 1
  if right != -1: inorder(right)

# 중위순환 실행
inorder(root_node)


# 각 노드의 level과 level에 속하는 노드들의 좌표 구하기
# 시작노드는 root node이다
queue = deque()
queue.append(root_node)
visited = [0 for _ in range(n+1)]
visited[root_node] = 1
level = [[] for _ in range(n+1)]
level[1].append(width[root_node])

while queue:

  node = queue.popleft()
  left = array[node][0]
  right = array[node][1]

  if left != -1:
    visited[left] = visited[node] + 1
    level[visited[left]].append(width[left])
    queue.append(left)
  if right != -1:
    visited[right] = visited[node] + 1
    level[visited[right]].append(width[right])
    queue.append(right)


# 가장 넓은 너비와 그 너비가 속하는 레벨 구하기
max_level = 0
max_width = 0

for i in range(1, max(visited)+1):
  if max_width < max(level[i])-min(level[i])+1:
    max_width = max(level[i])-min(level[i])+1
    max_level = i

# 결과 출력
print(max_level, max_width)

◼️ 중위순환을 이용해서 노드 별 좌표를 구하기

• 왼쪽 노드-> 부모 노드-> 오른쪽 노드 순으로 트리에 접근하는 중위순환을 이용하면 원하는 좌표값을 얻을 수 있다

◼️ BFS를 이용해서 각 level에 접근 & level 별 원소(노드의 좌표)를 구한다

◼️ level 리스트를 돌면서 max(level[i]) - min(level[i]) + 1을 이용하여 해당 level의 너비를 구하고, 최대 너비를 업데이트한다.

• 최대 너비(max_length)를 업데이트 할 때 max_level의 값 또한 현재의 level 값으로 업데이트 해준다.