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

유형 : 트리, 구현
난이도 : 중(상)

 

[예제 입력]

19
1 2 3
2 4 5
3 6 7
4 8 -1
5 9 10
6 11 12
7 13 -1
8 -1 -1
9 14 15
10 -1 -1
11 16 -1
12 -1 -1
13 17 -1
14 -1 -1
15 18 -1
16 -1 -1
17 -1 19
18 -1 -1
19 -1 -1

[예제 출력]

3 18

---

1. 내 풀이(미완성)

class Node:
    def __init__(self, data, left_node, right_node):
        self.data = data
        self.left_node = left_node
        self.right_node = right_node
        self.col = 0
        self.level = 0

array = []

def in_order(node):
    if node.left_node != -1:
        in_order(tree[node.left_node])
    print(node.data, end=' ')
    array.append(node.data)
    if node.right_node != -1:
        in_order(tree[node.right_node])


n = int(input())
tree = {}
for i in range(n):
    data, left_node, right_node = map(int,input().split())
    tree[data] = Node(data, left_node, right_node)

in_order(tree[1])

for i in range(1,n+1):
    tree[i].col = array.index(i)+1

for i in range(1,n+1):
    print(tree[i].col, end=' ')

▷ 중위순회를 이용해 열 번호를 파악할 수 있다는 것을 알았다.

    ▶ 위의 예시에서 중위순회를 거치면 "8 4 2 14 9 18 15 5 10 1 16 11 6 12 3 17 19 13 7"가 되는데, 이 순회 결과에서 인덱스와 열 번호가 같다는 것을 깨달았다. (정확히는 index+1 = 열 번호)

▷ 레벨을 구해야 하는데, 어떤 식으로 구현할 지 고민하다 해결하지 못하였다.

▷ 강의를 통해 풀이를 봤는데... 어렵다.. 다시 해보자!!

 

2. 다른 풀이

출처 : 패스트캠퍼스 - 알고리즘 / 기술면접 완전 정복 올인원 패키지 Online

 

▷  알고리즘의 시간복잡도 측면에서 그렇게 난이도가 높은 건 아니지만, 다소 구현 측면에서 난이도가 있다고 할 수 있다.

 

** 핵심 아이디어
1. 중위 순회를 이용하면 X축을 기준으로 왼쪽부터 방문한다는 특징이 있다.
2. 이 문제는 중위 순회 알고리즘을 이용하고, 추가적으로 Level 값을 저장하도록하여 문제를 해결할 수 있다.

 

class Node:
    def __init__(self, number, left_node, right_node):
    	self.parent = -1 # 노드 1번이 항상 루트가 아니라서 parent가 있는지 체크, parent없는 노드부터 순회
        self.number = number
        self.left_node = left_node
        self.right_node = right_node

def in_order(node):
    global level_depth, x
    level_depth = max(level_depth, level)
    
    if node.left_node != -1: # 왼쪽 노드 방문
    	in_order(tree[node.left_node], level+1)
    level_min[level] = min(level_min[level], x)
    level_max[level] = max(level_max[level], x)
    x += 1
    if node.right_node != -1: # 오른쪽 노드 방문
        in_order(tree[node.right_node], level+1)
        
n = int(input())
tree = {}
level_min = [n]
level_max = [0]
root = -1
x = 1
level_depth = 1

for i in range(1,n+1):
    tree[i] = Node(i, -1, -1) # 트리 초기화, 모두 비어있다고 가정
    level_min.append(n)
    level.max.append(0)
    
for _ in range(n):
    number, left_node, right_node = map(int, input().split())
    tree[number].left_node = left_node
    tree[number].right_node = right_node
    
    # 자식 노드 있으면 부모가 있다고 체크(부모 노드 값을 parent에 넣어줌)
    if left_node != -1:
    	tree[left_node].parent = number
    if right_node != -1:
    	tree[right_node].parent = number
        
for i in range(1, n+1):
    if tree[i].parent == -1: # 부모가 없는 노드 -> 루트
    	root = i
        
in_order(tree[root], 1)

result_level = 1
result_width = level_max[1] - level_min[1] + 1

for i in range(2, level_depth+1):
    width = level_max[i] - level_min[i] + 1 # 너비
    if result_width < width: # 가장 넓은 너비일 경우
    	result_level = i
        result_width = width
        
print(result_level, result_width)

 

 

문제 출처 : https://www.acmicpc.net/problem/2250

2250번: 트리의 높이와 너비