트리의 높이와 너비 ( 2250 번 )

2250번: 트리의 높이와 너비

 

 

---

🧠 알고리즘

• 트리 순회 + 중위 순회 기반 레벨별 너비 계산

 

✔️ 동작 방식

- 문제 핵심 아이디어
이진 트리를 “중위 순회(Inorder Traversal)”하며, 각 노드가 차지하는 열(column) 번호를 부여하고,
각 레벨(level) 별로 최소/최대 열 번호 차이를 계산하여 트리의 최대 너비와 그때의 레벨을 구하는 문제.

 

- 주요 로직 요약

1. 트리 구성 (_mk_conn)
   • 각 노드에 대해 [부모, 왼쪽 자식, 오른쪽 자식] 형태로 저장.
   • 부모가 없는 노드를 찾아 루트(root) 로 설정.
2. 중위 순회 (_dfs)
   • 전역 변수 col을 사용해 방문 순서대로 열 번호 부여.
   • 왼쪽 → 자기 자신 → 오른쪽 순서로 탐색.
   • 각 레벨(now_level)마다 해당 열 번호를 level 딕셔너리에 저장.
3. 결과 계산 (_main)
   • 각 레벨별로 (최대 열 - 최소 열 + 1)을 계산 → 그 레벨의 너비
   • 가장 너비가 큰 레벨과 그 너비를 출력.

---

 

🧾 코드

import sys

def _mk_conn(number):
    # [부모, 왼쪽 자식, 오른쪽 자식]
    answer = [[-1, -1, -1] for _ in range(number + 1)]
    for _ in range(number):
        a, b, c = map(int, sys.stdin.readline().rstrip().split())
        answer[a][1], answer[a][2] = b, c
        
        if b != -1:
            answer[b][0] = a
        if c != -1:
            answer[c][0] = a

    root = -1
    for idx in range(1, number + 1):
        if answer[idx][0] == -1:
            root = idx
            break
    return answer, root


def _dfs(node, now_level):
    global col
    
    if node == -1:
        return

    # 왼쪽
    _dfs(conn[node][1], now_level + 1)

    # 나 자신
    if now_level not in level:
        level[now_level] = []
    level[now_level].append(col)
    col += 1

    # 오른쪽
    _dfs(conn[node][2], now_level + 1)


# 최종 정답 출력
def _main(level_dict):
    answer, value = 0, 0
    for level_num in sorted(level_dict.keys()):
        now_value = max(level_dict[level_num]) - min(level_dict[level_num]) + 1
        if now_value > value:
            answer, value = level_num, now_value

    return f"{answer} {value}"


n = int(sys.stdin.readline().rstrip())
conn, now_root = _mk_conn(n)

# 전역 변수
col = 1 # 열 번호
level = {} # 레벨 : [열 번호]

# 중위 순회
_dfs(now_root, 1)

# 정답 출력
print(_main(level))

---

 

⏱️ 시간 복잡도

_mk_conn(number) : 트리 구성 ( 선형 시간 )
_dfs(now_root, 1) : 중위 순회, 각 노드 한번씩 탐색 ( 선형 시간 )
_main(level) : 최종 너비 및 레벨 계산 ( 선형 시간 )

해당 알고리즘 시간 복잡도 : 선형 시간 복잡도 ( O(n) )