[백준/dfs] 2250번: 트리의 높이와 너비(다시)

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

 

이진트리의 순회 방법을 처음 접해서 어떻게 풀어야할지 몰랐던 문제다

문제의 접근법은 중위순회이다. 

중위순회를 하면서 각 레벨에 따라 거리를 저장하는 것이 중요하다 

 

중위 순회란?

: 왼쪽 하위 트리부터 오른쪽 하위 트리 방향으로 방문하는 순회. 노드->부모노드->형제노드 순서로 진행하고,

예시로는 수식트리가 있다 

 

(1) 왼쪽 하위 트리부터 시작 : 가장 왼쪽의 '잎 노드'부터 시작한다는 말

(2) 루트

(3) 오른쪽 하위 트리 

 

-정답풀이: 

import sys
input=sys.stdin.readline

n=int(input())
graph=[[] for _ in range(n+1)] 

#루트 확인하는 리스트
isRoot=[0]*(n+1) 
root=0

#거리값 저장하는 리스트
distance=[[] for _ in range(n+1)] 


for _ in range(n):
    parent,left,right=map(int,input().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):
	#루트를 제외한 노드는 isRoot==2이다 
    if isRoot[i]==1:
        root=i
        
num=1
def inorder(start,deep): #deep은 레벨에 관련된 값, num은 거리에 관련된 값
    global num
    #왼쪽자식노드에 자식이 있을때
    if graph[start][0]!=-1: 
    	#왼쪽자식노드로 dfs진행 &깊이+1
        inorder(graph[start][0],deep+1)
    #해당 레벨(deep)에 해당하는 거리 삽입
    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)

 

 

-가장 이해가 가지 않는 부분: