[백준][C++] 2250 트리의 높이와 너비

www.acmicpc.net/problem/2250

2250번: 트리의 높이와 너비

 

 

 

알고리즘 종류

    - 트리

 

 

 

사고 과정

    - 노드에 맞춰 열의 번호가 매겨진 것을 보면 중위 순회임을 알 수 있다. 따라서 중위 순회를 하면서 각 층의 최소값과 최댓값을 구해주면 된다.

    

    - Root는 항상 1이 아니다. 예제에서 Root가 1로 제시되었지만, 어디에도 Root가 1부터 순서대로 입력된다는 말은 없다. 따라서 Root 노드를 찾아야 한다.

        1. 입력으로 부모노드, 자식노드1, 자식노드2가 주어진다.

        2. 각 노드가 입력된 횟수를 누적시킨다.

        3. 노드는 항상 부모가 됨으로 입력된 횟수는 1이다. 따라서, 횟수가 1인 노드를 찾는다.

 

 

 

구현(C++)

#include <iostream>
#include <vector>
#define MAX 987654321
 
using namespace std;
 
int n;
int col=1;
int maxDepth=0;
 
struct Node{
    int left=0;
    int right=0;
};
 
vector<int> maxNum, minNum;
vector<Node> tree;
vector<int> nodes;
 
 
void in_order(int p, int depth){
    
    if(depth > maxDepth) maxDepth = depth;
    
    if(tree[p].left != -1) in_order(tree[p].left, depth+1);
    
    // 깊이에 따라 최댓값과 최솟값을 저장한다.  
    maxNum[depth] = max(maxNum[depth], col);
    minNum[depth] = min(minNum[depth], col);
    col ++;
    
    if(tree[p].right != -1) in_order(tree[p].right, depth+1);
}
 
 
int main(void){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    
    cin >> n;
    
    tree.resize(n+1); // tree
    nodes.resize(n+1); // 자기 노드가 자식이 되는 경우  
    maxNum.resize(n+1); // 행의 최댓값  
    minNum.resize(n+1); // 행의 최솟값  
    for(int i=1; i<=n; i++) minNum[i] = MAX;
    
    
    int p, c1, c2;
    for(int i=0; i<n; i++){
        cin >> p >> c1 >> c2;
        
        nodes[p]++;
        
        if(c1 != -1) nodes[c1] ++;
        tree[p].left = c1;
        
        if(c2 != -1) nodes[c2] ++;
        tree[p].right = c2;
    }
    
    // 루트는 횟수가 1이 되지만, leaf 노드나 중간 노드는 횟수가 2가 된다.  
    int root;
    for(int i=1; i<=n; i++){
        if(nodes[i] == 1) 
            root = i;
    }
    
    // 중위 순회  
    in_order(root, 1); // 부모 노드, 깊이  
    
    // 각 행에서 너비 최댓값 찾기  
    int maxLength=0;
    int level=0;
    
    for(int i=1; i<=maxDepth; i++){
        int tmpLength = maxNum[i] - minNum[i] + 1;
        if(tmpLength > maxLength){
            maxLength = tmpLength;
            level = i;
        }
    }
    cout << level << " " << maxLength << endl;
}

 

 

 

시행착오

    - 첫 번째 시도에서 메모리 초과가 떴다. 포인터를 이용해서 왼쪽 자식과 오른쪽 자식을 저장하는 방법으로 트리를 생성했다. 그래서 메모리 초과가 발생했다. 배열로 트리를 구성하는 방법이 떠올랐다. 방법이 기억나지 않아서 검색을 통해 배열로 트리를 생성했다.

 

    - 첫 번째 시도에서 BFS를 이용해서 각 층을 방문하고 최솟값과 최댓값을 구했다. 그리고 Root는 항상 1이라고 생각했었다. 아래에 코드가 있다.

 

#include <iostream>
#include <queue>
 
using namespace std;
 
struct Node{
    int data;
    Node *left = NULL;
    Node *right = NULL;
};
 
int n;
int cnt=1;
 
int cols[10001];
 
 
void insert(Node *p, int c1, int c2){
    
    if(c1 != -1){
        Node *node = new Node;
        node->data = c1;
        p->left = node;
    }
    
    if(c2 != -1){
        Node *node = new Node;
        node->data = c2;
        p->right = node;
    }
}
 
 
Node *find_parent(Node* p, int data){
    
    queue<Node*> q;
    q.push(p);
    
    while(!q.empty()){
        
        Node *cn = q.front();
        q.pop();
 
        if(cn->data == data) return cn;
        else{
            if(cn->left != NULL) q.push(cn->left);
            if(cn->right != NULL) q.push(cn->right);
        }
    }
}
 
void in_order(Node* p){
    
    if(p != NULL){
        in_order(p->left);
        cols[p->data] = cnt++;
        in_order(p->right);
    }
}
 
void bfs(Node *root){
    
    queue<Node*> q;
    q.push(root);
    
    int row = 1;
    int maxLength=0;
    int maxRow=0;
    
    while(!q.empty()){
        
        int left=987654321;
        int right=0;
        int length=0;
        
        int size = q.size();
        while(size--){
            Node* tmp = q.front();
            q.pop();
            
            left = min(left, cols[tmp->data]);
            right = max(right, cols[tmp->data]);
            
            if(tmp->left != NULL) q.push(tmp->left);
            if(tmp->right != NULL) q.push(tmp->right);
            
        }
        
        length = right - left + 1;
        
        if(maxLength < length){
            maxLength = length;
            maxRow = row;
        }
 
        row++;
    }
    
    cout << maxRow << " " << maxLength << endl;
}
 
 
int main(void){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    
    cin >> n;
    
    int p, c1, c2;
    cin >> p >> c1 >> c2;
    
    Node *root = new Node;
    root->data = p;
    insert(root, c1, c2);
    
    
    for(int i=0; i<n-1; i++){
        
        cin >> p >> c1 >> c2;
        
        Node *tmp = find_parent(root, p);
        insert(tmp, c1, c2);
    }
    
    in_order(root);
    
    bfs(root);
}

 

    - 이번 문제를 통해서 배열로 트리를 생성하는 방법을 배울 수 있었다. 그리고 순회에서 매개변수로 깊이를 측정할 수 있는 것과 Root가 무슨 노드인지 찾는 방법을 배울 수 있었다.