[트리/구현] BAEKJOON '2250'번 '트리의 높이와 너비' 문제 (C++/python)

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

2250번: 트리의 높이와 너비

 

 

 

• 문제 해결 아이디어

1.  열의 순서는 inorder traversal 기준으로 탐색이 된다.

   

2.  inorder로 탐색을 하며, 해당 노드의 column값을 저장해주고( column_cnt ), 각 level별로 최대값( level_max[] ) 최소값( level_min[])을 계속 저장해준다.

   

3.  탐색은 항상 가장 윗 노드부터 시작해야되므로, root를 찾기위하여 parent변수를 선언해준다.

 

4.  level_max[i] 와 level_min[i]의 차이 중 가장 큰 값이 가장 넓은 너비이다.

 

 

• python

 

class Node:
    def __init__(self, data, left_node, right_node):
        self.data = data
        self.left_node = left_node
        self.right_node = right_node
        self.parent = -1



def inorder(node, lev):
    global column_cnt, depth
    depth = max(depth, lev)
    if node.left_node != -1:
        inorder(tree[node.left_node], lev+1)

    level_min[lev] = min(level_min[lev], column_cnt)
    level_max[lev] = max(level_max[lev], column_cnt)
    column_cnt += 1

    if node.right_node != -1:
        inorder(tree[node.right_node], lev+1)



n = int(input())
tree={}
level_min = [n]
level_max = [0]
column_cnt = 1
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):
    data, left_node, right_node = map(int,input().split())
    tree[data].left_node = left_node
    tree[data].right_node = right_node
    if left_node != -1:
        tree[left_node].parent = data
    if right_node != -1:
        tree[right_node].parent = data

for i in range(1, n+1):
    if tree[i].parent == -1:
        root = i

inorder(tree[root], 1)


result_width = -1
result_level = 0

for i in range(1, depth +1):
    width = level_max[i] - level_min[i]
    if result_width < width:
        result_width = width
        result_level = i

print(result_level, result_width+1)

 

 

• c++

c++에선 파이썬에서 처럼 dictionary변수를 사용할 수 없어서 구조체를 사용하였다.

(map함수로 해결하려 하였으나, key값이 중복이될 수 없기에 구조체 배열을 선언하였다.)

#include <iostream>
#include <algorithm>

using namespace std;

struct Node{
    Node* left;
    Node* right;
    int parent;
    int data;
};
Node* node;

int column_cnt = 1;
int depth = 0;  // 최고 높이를 저장하기 위해서 (그래프의 최종 높이), 결과 출력시 사용한다.


void inorder(Node *root, int lev, int level_min[], int level_max[]){
    depth = max(depth, lev);
    
    if(root->left)
        inorder(root->left, lev +1, level_min, level_max);
    
    level_min[lev] = min(level_min[lev], column_cnt);
    level_max[lev] = max(level_max[lev], column_cnt);
    column_cnt++;
    
    if(root->right)
        inorder(root->right, lev +1, level_min, level_max);
}




int main(){
    
    int n;
    int root_now, left_node, right_node;
    scanf("%d",&n);
    
    node = (Node*)malloc(sizeof(Node)*(n+1));
    int level_min[n+1];
    int level_max[n+1];
    
    for(int i=1 ; i< n+1 ; i++){
        node[i].parent = -1;
    }
    
    
    for(int i=0 ; i< n ; i++){
        cin >> root_now >> left_node >> right_node;
        node[root_now].data = root_now;
        if(left_node == -1)
            node[root_now].left = NULL;
        else{
            node[root_now].left = &node[left_node];
            node[left_node].parent = root_now;
        }
        if(right_node == -1)
            node[root_now].right = NULL;
        else{
            node[root_now].right = &node[right_node];
            node[right_node].parent = root_now;
        }
    }
    
    // level_min, level_max를 초기화하면서, root값을 찾는다.
    // parent가 초기화가 되어있지 않은 노드가 root
    int root = 0;
    for(int i= 1 ; i< n+1 ; i++){
        level_min[i] = n;
        level_max[i] = 0;
        if(node[i].parent == -1)
            root = node[i].data;
    }
    
    
    inorder(&node[root] , 1, level_min, level_max);
    
    
    int width;
    int result_width = -1, result_level=0;
    
    for(int i=1 ; i< depth + 1 ; i++){
        width = level_max[i] - level_min[i];
        if(result_width < width){
            result_width = width;
            result_level = i;
        }
        
    }
    
    printf("%d %d\n",result_level, result_width+1);
    
    return 0;
}