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

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

 

이진트리니까 부모노드는 최대 2개의 자식 노드를 가질 수 있다 

 

잎 노드가 아닐 때까지 연결 정보를 isRoot에 담은 뒤 이걸 바탕으로 root 노드를 찾는다 

루트노드부터 각 깊이별로 탐색해 가는 건 이해가 간다

 

너비는 같은 깊이에 있는 노드들의 컬럼 값 차이가 결정한다 

왼쪽 잎 노드가 나올때까지 dfs를 진행한다음, 왼쪽 잎 노드가 나오면 (data[start][0] == -1) 

그 노드의 깊이에 노드의 열 번호를 삽입한다. (특정 깊이에 해당하는 노드들의 열 번호가 삽입 된다)

잎 노드 dfs 끝나면 그 부모노드의 정보 삽입 되고, 그것의 오른쪽 노드로 진행된다,,,,

그래서 각 레벨에 해당되는 노드들의 열 번호들이 distance에 입력되고, 그 중 최댓값과 최솟값의 차이 중 최댓값을 출력하면된다

 

- 정답 풀이 : 

 

import sys
input = sys.stdin.readline

n = int(input())
data = [[] 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())
    data[parent].append(left)
    data[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):
    if isRoot[i] == 1:
        root=i

num = 1        
def dfs(start, depth) :
    global num
    if data[start][0] != -1:
        dfs(data[start][0], depth + 1)
    distance[depth].append(num)
    num += 1
    if data[start][1] != -1:
        dfs(data[start][1], depth+1)
        
dfs(root,1)
level = 1
answer = max(distance[1]) - min(distance[1]) + 1

for i in range(2,n+1):
    if distance[i] :
        large = max(distance[i])
        small = min(distance[i])
        if answer < large - small + 1:
            answer = large - small + 1
            # 너비가 큰 깊이를 저장함
            level=i
            
print(level,answer)