[BOJ] 2250 트리의 높이와 너비 바로가기
📍 문제
이진트리를 다음의 규칙에 따라 행과 열에 번호가 붙어있는 격자 모양의 틀 속에 그리려고 한다. 이때 다음의 규칙에 따라 그리려고 한다.
- 이진트리에서 같은 레벨(level)에 있는 노드는 같은 행에 위치한다.
- 한 열에는 한 노드만 존재한다.
- 임의의 노드의 왼쪽 부트리(left subtree)에 있는 노드들은 해당 노드보다 왼쪽의 열에 위치하고, 오른쪽 부트리(right subtree)에 있는 노드들은 해당 노드보다 오른쪽의 열에 위치한다.
- 노드가 배치된 가장 왼쪽 열과 오른쪽 열 사이엔 아무 노드도 없이 비어있는 열은 없다.
이와 같은 규칙에 따라 이진트리를 그릴 때 각 레벨의 너비는 그 레벨에 할당된 노드 중 가장 오른쪽에 위치한 노드의 열 번호에서 가장 왼쪽에 위치한 노드의 열 번호를 뺀 값 더하기 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)를 방문하고 마지막으로 오른쪽 트리를 방문하는 순회 방법이다. - 문제에서 요구한 것은 각 레벨에 존재하는 노드의 너비 중 가장 넓은 너비의 값과 해당하는 레벨의 값이다.
🧷 문제의 규칙에 따른 트리 위치
| 너비 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | 16 | 17 | 18 | 19 |
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| 노드의 번호 | 8 | 4 | 2 | 14 | 9 | 18 | 15 | 5 | 10 | 1 | 16 | 11 | 6 | 12 | 3 | 17 | 19 | 13 | 7 |
🧷 이진트리 중위 순회
| 너비 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | 16 | 17 | 18 | 19 |
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| 노드의 번호 | 8 | 4 | 2 | 14 | 9 | 18 | 15 | 5 | 10 | 1 | 16 | 11 | 6 | 12 | 3 | 17 | 19 | 13 | 7 |
- 🧷 문제의 규칙에 따른 트리 위치 와 🧷 이진트리 중위 순회 의 결과값이 같다는 것을 확인할 수 있다.
- 따라서 트리를 생성한 후 중위 순회를 통해 각 레벨에 해당하는 노드의 위치 값을 찾아서 가장 넓은 너비의 값을 찾으면 결과를 얻을 수 있다.
📌 문제 풀이
✏️ 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)