•
문제
이진트리를 다음의 규칙에 따라 행과 열에 번호가 붙어있는 격자 모양의 틀 속에 그리려고 한다. 이때 다음의 규칙에 따라 그리려고 한다.
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이다.
임의의 이진트리가 입력으로 주어질 때 너비가 가장 넓은 레벨과 그 레벨의 너비를 출력하는 프로그램을 작성하시오
풀이
•
기본 알고리즘
1. Tree를 입력받는다.
2. inorder traversal로 탐색한다
2.1 level마다 해당 level에 포함되는 data를 append해준다.
2.2 전체 inorder traversal에 해당하는 리스트를 저장한다.
3. level 마다 index(data[-1] - data[0])를 구하여 최대 너비를 구한다.
Python
복사
•
Node Class
- start : 순회의 시작점
class Node:
def __init__(self, data, left_node, right_node):
self.data = data # 자기 자신 data
self.left_node = left_node # left child
self.right_node = right_node # right child
self.parent = -1
Python
복사
•
traversal 함수
def trav(start, level):
global depth # 최대 깊이를 저장해주기 위한 변수
depth = max(depth, level)
levarr[level].append(start.data) # 해당 level에 data append
if start.left_node != -1: # 왼쪽 자식에 대해 inorder
trav(tree[start.left_node], level + 1)
arr.append(start.data) # inorder 순서대로 data append
if start.right_node != -1:
trav(tree[start.right_node], level + 1)
Python
복사
•
data 처리부분
n = int(input()) # 노드의 개수
levarr = [[]for _ in range(n+1)] # 각 레벨별 들어있는 node data
depth = 0 # 최대 높이를 기억
arr = [] # inorder 순서를 기억
tree = {} # tree
for i in range(1, n+1): # tree 초기화
tree[i] = Node(i, -1, -1)
for i in range(n):
root, left, right = map(int, input().split())
tree[root].left_node = left
tree[root].right_node = right
if left != -1: # root를 찾기 위한 parent 지정
tree[left].parent = root
if right != -1:
tree[right].parent = root
start = 0
for i in range(1, n+1): # parent가 없으면 root
if tree[i].parent == -1:
start = i
Python
복사
•
Main 동작
•
level마다 data가 들어가 있으므로 너비를 구하기 위해서는 index의 차를 구해야 한다!
따라서 전체 inorder의 list에서 해당 data의 index를 찾아서 너비를 계산함
trav(tree[start], 1) # level 1부터 시작하여 inorder 시작
maxlev = 1
maxwidth = 0
for i in range(1, depth + 1): # 모든 level 검사
if arr.index(levarr[i][-1]) - arr.index(levarr[i][0]) > maxwidth:
maxwidth = arr.index(levarr[i][-1]) - arr.index(levarr[i][0])
maxlev = i
print(maxlev, maxwidth + 1)
Python
복사
다른 풀이(inorder 중간과정에서 data가 아닌 index로 처리)
def trav(start, level):
global depth, pos
depth = max(depth, level)
if start.left_node != -1:
trav(tree[start.left_node], level + 1)
# 해당 부분에서 data를 처리해주는 것이 아닌 index로 처리해준다.
# 이렇게 하면 arr라는 별도의 inorder 전체가 담긴 리스트가 필요없어진다.
levarr[level].append(pos)
pos += 1
#
if start.right_node != -1:
trav(tree[start.right_node], level + 1)
for i in range(1, depth + 1):
if levarr[i][-1] - levarr[i][0] > maxwidth:
maxwidth = levarr[i][-1] - levarr[i][0]
maxlev = i
print(maxlev, maxwidth + 1)
Python
복사
중요
1.
트리 문제에서 root가 어디인지 지정되지 않는 경우엔 parent를 통해서 root를 찾을 수 있다!
2.
parent를 전부 -1로 초기화 한 후 tree를 입력받고 난 후에 여전히 parent가 -1인 것이 root!
for i in range(1, n+1):
tree[i] = Node(i, -1, -1, 0)
for i in range(n):
root, left, right = map(int, input().split())
tree[root].left_node = left
tree[root].right_node = right
if left != -1:
tree[left].parent = root
if right != -1:
tree[right].parent = root
start = 0
for i in range(1, n+1):
if tree[i].parent == -1:
start = i
Python
복사
2. List.index() 함수를 통해 List에서 특정 data의 index를 구할 수 있다.
maxwidth = arr.index(levarr[i][-1]) - arr.index(levarr[i][0])
Python
복사
