[백준] 2250번 : 트리의 높이와 너비

2250번: 트리의 높이와 너비

해당 문제는 이진 트리의 성질 중 “중위 순회” 법을 사용하여 문제를 해결 할 수 있다.

중위순회는 왼쪽노드 → 루트노트 → 오른쪽 노드를 순서대로 방문한다.

순서대로 방문했을때 각각의 노드와 x,y 좌표를 배열에 저장해 두었다가, 가장 큰 레벨을 찾으면 된다.

import sys
sys.setrecursionlimit(10000000)
N = int(input())
rootgraph = [[] for _ in range(N+1)]
graph = [[] for _ in range(N+1)]
graph2 = [[] for _ in range(N+1)]
for _ in range(N):
    root, left, right = map(int, input().split())
    # 자식노드 탐색 그래프
    graph[root].append(left)
    graph[root].append(right)
    
def findRoot():
    visited = [False for _ in range(N)]
    for i in range(1, N+1):
        for node in graph[i]:
            if node != -1 and not visited[node-1]:
                visited[node-1] = True
        
    return visited.index(False) + 1

distance = 1

def dfs(node, depth):
    global distance
    
    visited[node-1] = True
    leftnode = graph[node][0]
    rightnode = graph[node][1]
    
    if leftnode != -1 and not visited[leftnode-1]: #좌측 노드가 존재하면방문
        dfs(leftnode, depth + 1)
    
    graph2[depth].append((distance, node))
    distance += 1
        
    if rightnode != -1 and not visited[rightnode-1]: # 우측 노드가 존재하면 방문
        dfs(rightnode, depth + 1)

visited = [False for _ in range(N)]
dfs(findRoot(), 1)

maxvalue = 1
level = 1
for i in range(1, len(graph2)):
    graph2[i].sort()
    if len(graph2[i]) >= 2:
        cost = abs(graph2[i][0][0] - graph2[i][-1][0]) + 1
        if cost >= maxvalue:
            if cost == maxvalue:
                if level > i:
                    level = i
            else:
                maxvalue =  cost
                level = i
        
print(level, maxvalue)