[알고리즘] BOJ 2250 트리의 높이와 너비 #Python

김상현·2022년 11월 6일
0

알고리즘

목록 보기
223/301
post-thumbnail

[BOJ] 2250 트리의 높이와 너비 바로가기

📍 문제

이진트리를 다음의 규칙에 따라 행과 열에 번호가 붙어있는 격자 모양의 틀 속에 그리려고 한다. 이때 다음의 규칙에 따라 그리려고 한다.

  1. 이진트리에서 같은 레벨(level)에 있는 노드는 같은 행에 위치한다.
  2. 한 열에는 한 노드만 존재한다.
  3. 임의의 노드의 왼쪽 부트리(left subtree)에 있는 노드들은 해당 노드보다 왼쪽의 열에 위치하고, 오른쪽 부트리(right subtree)에 있는 노드들은 해당 노드보다 오른쪽의 열에 위치한다.
  4. 노드가 배치된 가장 왼쪽 열과 오른쪽 열 사이엔 아무 노드도 없이 비어있는 열은 없다.

이와 같은 규칙에 따라 이진트리를 그릴 때 각 레벨의 너비는 그 레벨에 할당된 노드 중 가장 오른쪽에 위치한 노드의 열 번호에서 가장 왼쪽에 위치한 노드의 열 번호를 뺀 값 더하기 1로 정의한다. 트리의 레벨은 가장 위쪽에 있는 루트 노드가 1이고 아래로 1씩 증가한다.

아래 그림은 어떤 이진트리를 위의 규칙에 따라 그려 본 것이다. 첫 번째 레벨의 너비는 1, 두 번째 레벨의 너비는 13, 3번째, 4번째 레벨의 너비는 각각 18이고, 5번째 레벨의 너비는 13이며, 그리고 6번째 레벨의 너비는 12이다.

우리는 주어진 이진트리를 위의 규칙에 따라 그릴 때에 너비가 가장 넓은 레벨과 그 레벨의 너비를 계산하려고 한다. 위의 그림의 예에서 너비가 가장 넓은 레벨은 3번째와 4번째로 그 너비는 18이다. 너비가 가장 넓은 레벨이 두 개 이상 있을 때는 번호가 작은 레벨을 답으로 한다. 그러므로 이 예에 대한 답은 레벨은 3이고, 너비는 18이다.

임의의 이진트리가 입력으로 주어질 때 너비가 가장 넓은 레벨과 그 레벨의 너비를 출력하는 프로그램을 작성하시오


📍 입력

첫째 줄에 노드의 개수를 나타내는 정수 N(1 ≤ N ≤ 10,000)이 주어진다. 다음 N개의 줄에는 각 줄마다 노드 번호와 해당 노드의 왼쪽 자식 노드와 오른쪽 자식 노드의 번호가 순서대로 주어진다. 노드들의 번호는 1부터 N까지이며, 자식이 없는 경우에는 자식 노드의 번호에 -1이 주어진다.


📍 출력

첫째 줄에 너비가 가장 넓은 레벨과 그 레벨의 너비를 순서대로 출력한다. 너비가 가장 넓은 레벨이 두 개 이상 있을 때에는 번호가 작은 레벨을 출력한다.


📍 풀이

💡 고찰

  • 풀이 방법을 알고나서 보면 너무나도 명확하게 보이지만, 모르고 보면은 도저히 방법을 생각해낼 수 없었다.
  • 이진 트리에서 순서에 대한 정보를 묻는다면 고려해야할 방법은 전위 순회(preorder), 중위 순회(inorder), 후위 순회(postorder) 이다.
  • 이번 문제에 적용한 방법은 중위 순회(inorder) 이다.
  • 중위 순회(inorder)란 왼쪽 하위 트리를 방문 후 뿌리(root)를 방문하고 마지막으로 오른쪽 트리를 방문하는 순회 방법이다.
  • 문제에서 요구한 것은 각 레벨에 존재하는 노드의 너비 중 가장 넓은 너비의 값과 해당하는 레벨의 값이다.

🧷 문제의 규칙에 따른 트리 위치

너비12345678910111213141516171819
노드의 번호84214918155101161161231719137

🧷 이진트리 중위 순회

너비12345678910111213141516171819
노드의 번호84214918155101161161231719137
  • 🧷 문제의 규칙에 따른 트리 위치🧷 이진트리 중위 순회 의 결과값이 같다는 것을 확인할 수 있다.
  • 따라서 트리를 생성한 후 중위 순회를 통해 각 레벨에 해당하는 노드의 위치 값을 찾아서 가장 넓은 너비의 값을 찾으면 결과를 얻을 수 있다.

📌 문제 풀이

✏️ 1. 중위 순회 함수

def inOrder(num, layer):
    global count
    left, right = nodes[num]
    if left != -1: inOrder(left, layer+1)
    layerList[layer].append(count)
    count += 1
    if right != -1: inOrder(right, layer+1)
  • 현재 노드(num)와 현재 레벨(layer)을 인자로 받는다.
  • 왼쪽, 루트, 오른쪽 순으로 중위 순회를 진행한다.
    • 만약 왼쪽 자식 노드가 존재한다면 왼쪽 자식 노드의 번호(left)와 현재 레벨(layer)에 1 을 더한값을 인자로 함수를 재귀한다.
    • 현재 노드의 위치를 현재 레벨(layer)에 해당하는 리스트에 추가한다.
    • 만약 오른쪽 자식 노드가 존재한다면 오른쪽 자식 노드의 번호(right)와 현재 레벨(layer)에 1 을 더한값을 인자로 함수를 재귀한다.

✏️ 2. 이진 트리 만들기

for value, left, right in edges:
    nodes[value][0] = left
    nodes[value][1] = right

    if left != -1: rootCandidate[left] += 1
    if right != -1: rootCandidate[right] += 1
  • 주어진 간선 정보(edges)를 통해 이진 트리를 생성한다.
  • 생성 도중에 루트 노드를 찾기 위해 부모 노드를 갖는 노드의 값은 1 증가시킨다.

✏️ 3. 루트 노드 찾기

for i in range(1,N+1):
    if rootCandidate[i] == 0:
        root = i
  • 부모 노드의 개수의 값을 갖는 rootCandidate 리스트에서 부모 노드를 갖지 않는 즉, 0의 값을 갖는 노드를 root 노드로 정한다.

✏️ 4. 중위 순회

inOrder(root,1)
  • 위에서 찾은 루트 노드(root)의 값과 레벨 초기값(1)을 인자로 중위순회를 실행한다.

✏️ 5. 너비가 가장 넓은 레벨과 그 레벨의 너비 탐색

for key in sorted(layerList):
    values = layerList[key]
    width = max(values) - min(values) + 1
    if WIDTH < width:
        LAYER, WIDTH = key, width
return LAYER, WIDTH
  • 각 레벨 별 가장 넓은 너비의 값(max(values) - min(values) + 1)을 구한 후 현재까지 구한 값 중 가장 넓다면 해당 레벨의 값(key)과 너비의 값(max(values) - min(values) + 1)을 LAYER, WIDTH에 저장한다.
  • 모든 탐색이 종료되면 결과를 반환한다.

✍ 코드

from sys import stdin
from collections import defaultdict

count = 1

def solution(N,edges):

    LAYER, WIDTH = 0, 0
    layerList = defaultdict(list)
    nodes = [[None,None] for _ in range(N+1)]
    rootCandidate = [0] * (N+1)

    # [0] 중위 순회 함수
    def inOrder(num, layer):
        global count
        left, right = nodes[num]
        if left != -1: inOrder(left, layer+1)
        layerList[layer].append(count)
        count += 1
        if right != -1: inOrder(right, layer+1)

    # [1] 이진트리 만들기
    for value, left, right in edges:
        nodes[value][0] = left
        nodes[value][1] = right

        if left != -1: rootCandidate[left] += 1
        if right != -1: rootCandidate[right] += 1

    # [2] root 노드 찾기
    for i in range(1,N+1):
        if rootCandidate[i] == 0:
            root = i

    # [3] 중위 순회
    inOrder(root,1)

    # [4] 너비가 가장 넓은 레벨과 그 레벨의 너비 탐색
    for key in sorted(layerList):
        values = layerList[key]
        width = max(values) - min(values) + 1
        if WIDTH < width:
            LAYER, WIDTH = key, width

    return LAYER, WIDTH

N = int(stdin.readline())
edges = [list(map(int,stdin.readline().split())) for _ in range(N)]

layer, width = solution(N,edges)
print(layer, width)
profile
목적 있는 글쓰기

0개의 댓글