2250. 트리의 높이와 너비

문제 링크

2250. 트리의 높이와 너비

코드

from collections import deque

node = int(input())

node_list =[]
node_idx_list =[]
child_node_list =[]

for tmp_node in range(node):
    num_list = list(map(int,input().split()))
    node_list.append(num_list)
    node_idx_list.append(num_list[0]) # 루트부터 들어오지 않는 경우도 있어서 node idx list를 만들어서 보관해야함 
    if num_list[1] !=-1: # -1이 아니면 자식노드 리스트에 추가
        child_node_list.append(num_list[1])
    if num_list[2] != -1:
        child_node_list.append(num_list[2])


for i in node_idx_list:
    if i not in child_node_list:
        root_node = i #자식 노드 리스트에 없는 노드가 루트 노드임 

idx = 0
level_left=[0]*node # 레벨에서 가장 왼쪽에 있는 노드
level_right=[0]*node # 레벨에서 가장 오른쪽에 있는 노드 

que =deque() # 노드 리스트를 보관하는 큐
result_que = deque() # 문제에서 주어진 트리의 순서대로 노드를 배치하는 큐 

root_node_idx = node_idx_list.index(root_node) #찾은 root의 idx를 통해서 처음 시작 root node를 정해준다. 

result_que.append(node_list[root_node_idx][0])

level = 1
idx = 0

tmp_que = deque() #레벨을 부여해주기 위해 임시로 사용하는 큐 
tmp_que.append([0,node_list[root_node_idx]])
que.append([0,node_list[root_node_idx]])
while len(tmp_que)>0:
    tmp_node = tmp_que.popleft()
    tmp_level = tmp_node[0]
    left_node = tmp_node[1][1]
    right_node = tmp_node[1][2]

    if left_node != -1: #레벨을 부여해주는 작업을 수행하고, que에 넣는다. 
        left_node_idx = node_idx_list.index(left_node)
        tmp_que.append([tmp_level+1,node_list[left_node_idx]])
        que.append([tmp_level+1,node_list[left_node_idx]])
    if right_node != -1:
        right_node_idx = node_idx_list.index(right_node)
        tmp_que.append([tmp_level+1,node_list[right_node_idx]])
        que.append([tmp_level+1,node_list[right_node_idx]])


same_level_node =[] #level 마다 존재하는 노드들을 구분하기 위한 리스트 
same_level = 0
for i in range(len(que)):
    now = que[i]
    level = now[0]
    now_node = now[1][0]

    if same_level != level:
        if len(same_level_node)> 0:
            level_left[level-1] = same_level_node[0]
            level_right[level-1] = same_level_node[-1]

        same_level_node =[]
        same_level = level

    same_level_node.append(now_node)

#동일한 레벨에서 가장 왼쪽 값과 가장 오른쪽 값이 어딘지 확인하고 level_left or right에 넣어준다. 
level_left[level] = same_level_node[0] 
level_right[level] = same_level_node[-1]

while len(que)>0: #문제에서 주어진 트리대로 배치하는 방법 
    tmp = que.popleft()
    tmp_level = tmp[0]
    tmp_node = tmp[1][0]
    left_node = tmp[1][1]
    right_node = tmp[1][2]
    result_tmp_idx = result_que.index(tmp_node)

    if left_node != -1:
        if result_tmp_idx ==0:
            result_que.appendleft(left_node)
        else:
            result_que.insert(result_tmp_idx,left_node)
        result_tmp_idx +=1


    if right_node != -1:
        result_que.insert(result_tmp_idx+1,right_node)


level_length =[0]*node

for i in range(len(level_left)): #각각의 레벨별로 왼쪽값의 index와 오른쪽 값의 index를 구하고 차이값을 level_length에 저장한다. 
    if level_left[i] !=0:
        left_idx = result_que.index(level_left[i]) 
        right_idx = result_que.index(level_right[i])
        level_length[i] = right_idx-left_idx+1



maxist = 0
max_idx = 0

for i in range(len(level_length)): #가장 높은 값을 찾아주고, 동일할 경우에는 패스하도록 설정 
    if level_length[i] > maxist:
        maxist = level_length[i]
        max_idx = i

print(str(max_idx+1)+" "+str(maxist))

문제 풀이

• 예시에는 root node가 1번부터 시작하고 맨 위에 존재하지만, 문제 case에는 root node부터 시작하지 않을 수도, node의 순서대로 들어오지 않을 수 있다.

• level을 2**level - 1 방식으로 해보려고 했는데 완전 이진트리가 아니기 때문에 이 방식으로 레벨을 부여해서는 안된다.

• 큐를 이용해서 레벨을 부여, 다만 완전한 node 순서를 보유하고있는 que도 필요하므로 tmp_que를 선언해서 node마다 레벨을 부여했다.

• 부여된 레벨을 이용해서 레벨별 왼쪽 끝 노드와 오른쪽 끝 노드를 구한다.

• 루트노드에서 좌우 Child node를 정해주기때문에, 입력데이터가 아무렇게나 들어와도 que에는 노드 순서대로 들어가 있다.

• 따라서 동레벨의 가장 왼쪽 값과 오른쪽값만 구하면 된다.

• 문제에서 주어진 트리대로 배치하고 idx만 찾아서 계산해주면 된다.