백준 2250번 : 트리의 높이와 너비 - 트리, C++

https://www.acmicpc.net/problem/2250

2250번: 트리의 높이와 너비

#include <bits/stdc++.h>
using namespace std;
const int MX = 10003;

int column[MX] , N, root , order, totalLev;
int adj[MX][2], revAdj[MX][2];
vector<int> level[MX];


//root 노드 찾기
int findRoot(int node){
    bool ch[N+1];
    memset(ch, 0 , sizeof(ch));
    queue<int> Q;

    ch[node] = 1;
    Q.push(node);
    while(!Q.empty()){
        int cur = Q.front(); Q.pop();
        if(revAdj[cur][0] == 0 && revAdj[cur][1] == 0){
            return cur;
        }

        for(int i=0; i<2; i++){
            int nxt = revAdj[cur][i];
            if(nxt == 0 || nxt == -1) continue;

            if(!ch[nxt]){
                ch[nxt] = 1;
                Q.push(nxt);
            }
        }
    }
    return -1;
}

void getLevel(int node){
    bool ch[N+1];
    memset(ch, 0 , sizeof(ch));

    queue<int> Q;

    ch[node] = 1;
    Q.push(node);

    while(!Q.empty()) {
        int curSize = Q.size();
        totalLev++;
        for(int i=0; i<curSize; i++){
            int cur = Q.front(); Q.pop();
            level[totalLev].push_back(cur);

            for(int j=0; j<2; j++){
                int nxt = adj[cur][j];
                if(nxt == 0 || nxt == -1) continue;
                if(!ch[nxt]){
                    ch[nxt] = 1;
                    Q.push(nxt);
                }
            }
        }
    }
}


void inOrder(int node){
    if(node == -1) return;
    inOrder(adj[node][0]);
    column[node] = ++order;
    inOrder(adj[node][1]);
}


int main() {
    ios::sync_with_stdio(0); cin.tie(0);

    cin >> N;

    for(int i=0; i<N; i++){
        int a, b, c;
        cin >> a >> b >> c;
        adj[a][0] = b;
        adj[a][1] = c;

        revAdj[b][0] = a;
        revAdj[c][1] = a;
    }

    root = findRoot(N);

    getLevel(root);
    inOrder(root);

    int ansLev = 0, ansWidth = 0;

    for(int i=1; i<=totalLev; i++){
        int minn = 10003, maxx = -1;

        for(auto num : level[i]){
            minn = min(column[num], minn);
            maxx = max(column[num], maxx);
        }

        int curWidth = maxx - minn + 1;

        if(curWidth > ansWidth){
            ansWidth = curWidth;
            ansLev = i;
        }
    }
    
    cout << ansLev << ' ' << ansWidth <<'\n';




    return 0;
}