문제 : https://www.acmicpc.net/problem/2250

풀이

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)