백준 2250번. 트리의 높이와 너비(c++) / Tree

전형적인 Tree문제이다.

InorderTraversal(중위순회)을 통해서 col값을 ++해주고

dfs를 통해서 인자값으로 넘긴 level을 기준으로 height[level]값에 해당 col값을 차례대로 넣어주었다.

이후에는 1~maxHeight값을 탐색하며 level별로 너비를 구해주며, 최대 너비를 구했다.

 

// 트리의 높이와 너비
#include <iostream>
#include <algorithm>
#include <vector>
 
using namespace std;
 
pair<int, int> tree[10001];
int n, m, a, b, root;
int cnt[10001] = {0, };
int idx = 0, maxHeight = 0;
vector<int> height[10001];
 
bool cmp(const pair<int, int> &a, const pair<int, int> &b){
    if(a.first==b.first){
        return a.second<b.second;
    }
 
    return a.first>b.first;
}
 
void InorderTraversal(int node, int level){
    if(node==-1){
        return;
    }
    maxHeight = max(maxHeight, level);
    InorderTraversal(tree[node].first, level+1);
    height[level].push_back(idx++);
    InorderTraversal(tree[node].second, level+1);
}
 
int main()
{
    cin>>n;
    for(int i=1; i<=n; i++){
        cin>>m>>a>>b;
        tree[m] = make_pair(a, b);
        cnt[m]++;
        cnt[a]++;
        cnt[b]++;
    }
 
    for(int i=1; i<=n; i++){
        if(cnt[i]==1){
            root = i;
            break;
        }
    }
 
    InorderTraversal(root, 1);
 
    vector<pair<int, int>> temp;
    for(int i=1; i<=maxHeight; i++){
        int width = height[i][height[i].size()-1]-height[i][0]+1;
        temp.push_back(make_pair(width, i));
    }
    sort(temp.begin(), temp.end(), cmp);
 
    cout<<temp[0].second<<" "<<temp[0].first<<"\n";
    return 0;
}