[백준,c++] 2250번 - 트리의 높이와 너비

문제

2250번: 트리의 높이와 너비

 

코드

#include <iostream>
#include <vector>
#include <unordered_map>
#include <algorithm>

using namespace std;

vector<pair<int,int>>graph[10001];
unordered_map<int,int> cnt;
vector<int> height_arr[10001];

int N, root;
int col[10001];
int seq = 1;
int height = 1;

void inorder(int node){
    
    for(auto next: graph[node]){
        if(next.first != -1){
            height++;
            inorder(next.first);
            height--;
        }
        height_arr[height].push_back(node);
        col[node] = seq++;
        
        if(next.second !=-1){
            height++;
            inorder(next.second);
            height--;
        }
    }
}

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    
    cin>>N;
    for(int i=0; i<N; i++){
        int node, first, second;
        cin>>node>>first>>second;
        graph[node].push_back({first,second});
        cnt[node]++;
        cnt[first]++;
        cnt[second]++;
    }
    
    for(auto it = cnt.begin(); it!=cnt.end(); it++){
        if(it->second == 1){
            root = it->first;
            break;
        }
    }
    inorder(root);
    
    int ans_height = 0, ans_width = 0;
    
    for(int i=0; i<=N; i++){
        if(height_arr[i].empty()) continue;
        int width = col[height_arr[i].back()] - col[height_arr[i].front()] + 1;
        int height = i;
        if(width>ans_width){
            ans_width = width;
            ans_height = height;
        }
    }
    cout<<ans_height << ' '<<ans_width;
}

 

풀이

이진트리 탐색 운행법

문제 설명의 이미지를 잘 보면 세로열은 깊이, 가로 열은 중위 순회(inorder)의 순서인 것을 알 수 있습니다.

• 루트 노드의 경우는 단 한 번만 입력값으로 들어온 노드가 루트 노드입니다.
• 그 후 각 중위 순회 방식으로 트리를 순회하여 각 노드마다 가로 열의 위치(너비)와 세로열의 위치(깊이)를 저장해줍니다.
• 그 후, 높이만큼 루프를 돌아 가장 긴 너비를 찾아서 출력하면 됩니다.