풀이
1. 루트 노드 찾기
- 트리에서 루트 노드는, 입력받을 때 한번도 자식 노드로 선언되지 않은 노드라고 할 수 있다.
- 1 ··· N 까지의 bool 값이 들어있는 리스트를 만들고 자식으로 입력될 때 해당 인덱스 값을 True로 변경하면, 루트노드 하나를 제외한 나머지 노드는 모드 True 값을 갖게 된다.
- 즉 입력을 전부 받은 후 값이 False인 인덱스가 루트 노드이다.
2. 트리 탐색하기
- 왼쪽 -> 부모 -> 오른쪽 순으로 탐색하므로, 기본적으로 중위 순회이다.
- 모든 노드가 몇번째 열에 해당하는지 찾을 필요 없이, 각 깊이(행)별로 최소 열값과 최대 열값만 찾으면 된다.
- 각 노드의 열 번호는 해당 노드를 중위 순회했을 때 탐색 순서와 같다.
- 즉, 각 깊이 별로 최소 열 번호, 최대 열 번호를 저장하는 이차원 리스트를 하나 만들고, 노드를 탐색할 때 마다 갱신해주면 된다.
- 두번째 탐색순서로 4번 노드를 방문했을 경우 깊이 3에 대해서 처음으로 방문했으므로, 최소 열 번호는 2, 최대 열 번호도 2가 된다.
-
이어서 다른 노드를 차례차례 방문하다가 8번째 순서로 5을 방문했을 경우
최소 열 번호는 그대로 2이지만, 최대 열 번호는 8로 갱신된다. -
이런 식으로 모든 트리를 탐색하면, 각 깊이에 대한 최소 열 번호, 최대 열 번호를 얻을 수 있다.
3. 답 출력하기
- 이제 깊이별로
최대 열 번호 - 최소 열 번호 + 1을 구하면 너비를 구할 수 있다. - 출력할 답을 최소값으로 설정해 두고, 답이 갱신될 때마다 몇번째 깊이인지 저장하면 너비가 가장 긴 레벨과 길이를 모두 구할 수 있다.
- 길이가 같다면 작은쪽을 출력해야하므로, 기존 최소 길이보다 길이값이 더 작을때만 갱신하면 된다.
코드
import sys
input = sys.stdin.readline
def DFS(depth, node):
global col_num
left, right = tree[node]
# 중위 순회
if left != -1:
DFS(depth+1, left)
max_width[depth][0] = min(max_width[depth][0], col_num)
max_width[depth][1] = max(max_width[depth][1], col_num)
col_num += 1
if right != -1:
DFS(depth+1, right)
N = int(input())
tree = [() for _ in range(N+1)]
is_child = [False] * (N+1)
# 0. 입력 받기 (루트 찾을 수 있도록 is_child 리스트 갱신)
for _ in range(N):
parent, left, right = map(int, input().split())
tree[parent] = (left, right)
if left != -1:
is_child[left] = True
if right != -1:
is_child[right] = True
# 1. 루트 노드 찾기
start = is_child[1:].index(False) + 1
# 2. 트리 순회하면서 각 깊이별로 최소 열 번호, 최대 열 번호 찾기
max_width = [[2147000000, 0] for _ in range(N)]
col_num = 1
DFS(0, start)
# 3. 최대 너비를 갖는 레벨과 그 길이 찾고 출력하기
answer_row = 0
answer_width = 0
for i in range(N):
min_col, max_col = max_width[i]
if max_col == 0:
break
temp = max_col - min_col + 1
if temp > answer_width:
answer_width = temp
answer_row = i+1
print(answer_row, answer_width)
