💡 문제
이진트리를 다음의 규칙에 따라 행과 열에 번호가 붙어있는 격자 모양의 틀 속에 그리려고 한다. 이때 다음의 규칙에 따라 그리려고 한다.
- 이진트리에서 같은 레벨(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이 주어진다.
출력
첫째 줄에 너비가 가장 넓은 레벨과 그 레벨의 너비를 순서대로 출력한다. 너비가 가장 넓은 레벨이 두 개 이상 있을 때에는 번호가 작은 레벨을 출력한다.
💭 접근
처음 이 문제를 보았을 때 그림과 같이 각 트리의 노드에 2차원 좌표를 저장하여 문제를 풀어 보려했지만 쉽지 않아 힌트를 찾아보았다. 그 결과 트리에 대해서 중위 순회를 하게 되면 위 그림과 같이 가로번호가 매겨지게 된다는 것을 알았다. 따라서 다음과 같은 순서로 문제를 해결하였다.
- 트리 입력받기 및 루트노드 찾기
n = int(input())
tree = [[0, 0, 0, 0, 0] for _ in range(n + 1)] # left, right, parent, level, width
for _ in range(n):
node, left, right = map(int, input().split())
if left == -1:
left = 0
if right == -1:
right = 0
tree[node][0] = left
tree[node][1] = right
tree[left][2] = node
tree[right][2] = node
for i in range(1, n + 1):
if tree[i][2] == 0:
root = i트리의 각 노드에 왼쪽자식, 오른쪽자식, 부모, 레벨, 너비를 저장해준다. 이후, 최대 레벨을 구하기 위해 루트노드를 찾아 준다.
- 각 노드에 레벨을 저장해주고 최대 레벨을 구한다.
def dfs(start, level):
global max_level
visited[start] = True
tree[start][3] = level
max_level = max(max_level, level)
for next in range(2):
if not visited[tree[start][next]]:
dfs(tree[start][next], level + 1)- 중위 순회를 통해 각 노드에 너비를 저장해준다.
def inorder(node):
global order
if node:
inorder(tree[node][0])
tree[node][4] = order
order += 1
inorder(tree[node][1])- 각 레벨의 최대 너비를 구한 다음, 정답 출력
level_width = [[] for _ in range(max_level + 1)]
for i in range(1, n + 1):
level_width[tree[i][3]].append(tree[i][4])
ans = []
for i in range(1, max_level + 1):
ans.append(max(level_width[i]) - min(level_width[i]))
print(ans.index(max(ans)) + 1, max(ans) + 1)📒 코드
# 이진 트리를 돌면서 번호를 매겨준다.
def dfs(start, level):
global max_level
visited[start] = True
tree[start][3] = level
max_level = max(max_level, level)
for next in range(2):
if not visited[tree[start][next]]:
dfs(tree[start][next], level + 1)
# 이진트리를 돌면서 트리의 깊이를 매겨준다.
def inorder(node):
global order
if node:
inorder(tree[node][0])
tree[node][4] = order
order += 1
inorder(tree[node][1])
n = int(input())
tree = [[0, 0, 0, 0, 0] for _ in range(n + 1)] # left, right, parent, level, width
for _ in range(n):
node, left, right = map(int, input().split())
if left == -1:
left = 0
if right == -1:
right = 0
tree[node][0] = left
tree[node][1] = right
tree[left][2] = node
tree[right][2] = node
# 루트 번호 찾기 (부모가 없은 노드가 루트이므로)
for i in range(1, n + 1):
if tree[i][2] == 0:
root = i
# 깊이의 최대치 찾기
visited = [False for _ in range(n + 1)]
visited[0] = True
max_level = 0
dfs(root, 1)
# 노드에 순서(너비) 매기기
order = 1
inorder(root)
# 각 레벨의 너비를 구하기 위해 각 노드가 해당하는 깊이에 해당 노드의 너비를 append
level_width = [[] for _ in range(max_level + 1)]
for i in range(1, n + 1):
level_width[tree[i][3]].append(tree[i][4])
ans = []
for i in range(1, max_level + 1):
ans.append(max(level_width[i]) - min(level_width[i]))
print(ans.index(max(ans)) + 1, max(ans) + 1)💭 후기
중위 순회를 하고 나면 각 노드의 너비(순서)를 매길 수 있다는 것을 알았다.
🔗 문제 출처
https://www.acmicpc.net/problem/2250
