백준: 2250 트리의 높이와 너비

문제

2250번: 트리의 높이와 너비

 

문제 풀이

 트리가 주어질 때, 가장 넓이가 높은 경우에 레벨과 넓이를 찾는 문제이다. 입력 예제의 그림을 보면 1을 기준으로 left child부터 인덱스가 할당되고, 1의 인덱스를 할당한 후에 right child의 인덱스를 할당하는 것을 알 수 있다. 이는 중위 순회를 통해 트리의 인덱스 번호를 부여한 것이라는 걸 알 수 있다. 중위 순회의 경우 트리 순회 문제에서 다루었다. 문제를 풀기 위해 다음과 같은 과정을 진행하면 답을 구할 수 있다.

 

• 트리를 중위 순회하며 인덱스 번호 부여하고 레벨(depth) 별로 구분
• 레벨 1부터 N까지 인덱스차가 가장 많이 나는 레벨과, 인덱스 차를 반환

 

코드

from sys import stdin


def in_order(node, level):
    global idx
    left, right = graph[node].values()
    if left != -1:
        in_order(left, level + 1)

    node_per_level[level].append(idx)
    idx += 1

    if right != -1:
        in_order(right, level + 1)


if __name__ == '__main__':
    n = int(stdin.readline())
    graph = dict()
    parent_check = [False] * n
    node_per_level = [[] for _ in range(n)]
    idx = 1

    # 그래프 정보 초기화, Parent 정보 체크
    for _ in range(n):
        node, left, right = map(int, stdin.readline().split())

        if left != -1:
            parent_check[left - 1] = True
        if right != -1:
            parent_check[right - 1] = True
        graph[node] = {'l': left, 'r': right}

    # root 노드를 찾음.
    root = parent_check.index(False) + 1

    # 중위 순회를 통해, 각 레벨별로 인덱스를 분류함
    in_order(root, 0)

    max_level, max_level_width = 0, 0

    # 레벨 별로 인덱스의 차를 계산하고, 가장 큰 경우를 찾음
    for level, nodes in enumerate(node_per_level):
        if nodes:
            width = max(nodes) - min(nodes) + 1
            if max_level_width < width:
                max_level_width = width
                max_level = level + 1

    print(max_level, max_level_width)

 N이 1인 경우를 반영하지 못해, 92% 쯤에서 틀렸다고 하여 N이 1인 경우도 반영하자 맞았습니다!! 를 볼 수 있었다.😀