2250번 트리의 높이와 너비 백준 파이썬

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

2250번: 트리의 높이와 너비

이 문제를 처음 접근했을 때 중위순회의 접근까지 좋았으나 중위 순회를 통해 저장하는 것을 레벨당 좌표가 아닌 각 좌표들이 어느 거리에 있나 저장해서 꼬인 것 같다.

 

이 문제의 접근법은 중위순회이다.  그리고 이 중위순회를 통해 각 레벨에 따라 거리를 저장하는 것 이것이 중요한 관점이다.

 

import sys
from collections import deque
N=int(sys.stdin.readline())
graph=[[] for _ in range(N+1)] ## 그래프
isRoot = [0]*(N+1) ## 루트확인하는 리스트
distance= [[] for _ in range(N+1)] ## 거리값 저장하는 리스트
root=0
for _ in range(N):
    parent,left,right=map(int,sys.stdin.readline().rstrip().split())
    graph[parent].append(left)
    graph[parent].append(right)
    isRoot[parent]+=1
    if left!=-1:
        isRoot[left]+=1
    if right!=-1:
        isRoot[right]+=1
for i in range(1,N+1): #루트를 제외한 모든 점들은 2의 값을 가지기 때문에
    if isRoot[i]==1:
        root=i
num=1
def inorder(start,deep): #deep은 레벨에 관련된 값, num은 거리에 관련된 값이다.
    global num
    if graph[start][0]!=-1:
        inorder(graph[start][0],deep+1)
    distance[deep].append(num)
    num+=1
    if graph[start][1]!=-1:
        inorder(graph[start][1],deep+1)

inorder(root,1)
level=1
ans= max(distance[1])-min(distance[1])+1
for i in range(2,N+1):
    if distance[i]:
        small=min(distance[i]) ## 각 층마다의 거리를 계산하여 최댓값인지 확인한다.
        large=max(distance[i])
        if ans<large-small+1:
            ans=large-small+1
            level=i
print(level)
print(ans)

참고:https://pacific-ocean.tistory.com/331

[백준] 2250번(python 파이썬)