"""
이 문제는 중위순회 하는 순서가 곧 행(가로)의 인덱스를 의미한다..
"""
import sys
input=sys.stdin.readline
sys.setrecursionlimit(10**9)
def DFS(root,level): #중위순회
global time #깊이를 저장할 변수
if Tree[root][0]!=-1: #탐색 가능하다면 탐색한다.
DFS(Tree[root][0],level+1)
distance[level].append(time) #중위순회이기때문에 중간지점에서 리스트 값 추가.
time+=1 # 리스트 값 추가시 깊이+1
if Tree[root][1] != -1:
DFS(Tree[root][1],level+1)
N=int(input())
Tree={}
check_root=[0]*(N+1) # 루트노드는 꼭 1이 아님.
for i in range(N):
a,b,c=map(int,input().split())
Tree[a]=[b,c] #left,right
check_root[a]+=1
if b!=-1:
check_root[b]+=1
if c!=-1:
check_root[c]+=1
for i in range(1,N+1):
if check_root[i]==1: #한번만 나온지점은 부모노드가 없다는 뜻이므로 루트노드이다.
start=i # 루트노드 찾기
distance= [[] for _ in range(N+1)] ## 거리값 저장하는 리스트
time=1 ; index=1 ; total=0 # 각각 깊이를 저장할 변수 , 인덱스 위치(가로) , 최대값
DFS(start,1)
for i in range(N+1):
if distance[i]:
if total<max(distance[i])-min(distance[i])+1: #새로운 값이 발견되면
total=max(distance[i])-min(distance[i])+1 #total을 갱신해준다.
index=i #그때의 인덱스 위치도 저장한다.
print(index,total)📌 어떻게 접근할 것인가?
문제에서 원하고자 하는 값은 같은 행(가로줄) 에 존재하는 노드들의 인덱스 차이의 최대값 과 그때의 깊이를 구하는 것이다.
문제에서는 노드 4 와 7 이 깊이 3이고 인덱스 차이는 19-2+1=18 이다.
이때 인덱스 차이를 구할때 마지막에 1을 구해야한다.
📌 그림에 숨겨진 요소
인덱스 차이를 구할때 문제점은 깊이는 1씩 더해가며 탐색하면 되지만 인덱스를 구하는 것이 문제이다.
그림을 잘 보면 왼쪽-루트-오른쪽 노드 를 탐색하는 순서대로 인덱스가 증가한다.
즉 인덱스란 곧 중위순회의 순서를 의미한다.
따라서 중위순회를 그대로 적용시켜주면된다.
또 주의해야할 점은 꼭 루트노드가 1이 아니라는 지점이다.
따라서 루트노드를 찾는 작업을 꼭 해줘야 한다.
✅ 느낀점
이 문제가 중위순회라는 걸 알아차리지 못한게 정말 아쉬웠다.
그부분만 이해하면 단순 구현문제 이기 때문에 한번에 AC 를 받지 못헀다.
트리 문제를 더 많이 풀면서 이해력을 높여야겠다.
