[ BOJ 백준 2250번 - 트리의 높이와 너비 ] 해설 및 코드

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

목적

입력으로 주어지는 노드의 정보로 트리구조를 형성하고, 각 레벨의 너비가 최대인 레벨과 너비를 구하자.

 

접근법

1. DFS를 이용하여 왼쪽 자식, 부모, 오른쪽 자식 순으로, 트리의 각 노드에 열번호를 지정한다.

2. 번호를 지정하면서 레벨 정보를 같이 넘겨주어, 각 레벨의 좌우 양 끝 노드의 열 번호를 갱신한다.

 

#include<bits/stdc++.h>
#define LEN 10001
#define f(i,l,r) for(int i=l;i<=r;i++)
using namespace std;
 
int n,t[LEN][3],s[LEN+1][2]{};
 
void calc(int i,int lev){
    if(i==-1)return;
    calc(t[i][2],lev+1);
    s[lev][0]=min(s[lev][0],n);
    s[lev][1]=max(s[lev][1],n);
    t[i][2]=n--;
    calc(t[i][1],lev+1);
}
 
int main(){
    ios_base::sync_with_stdio(0); cout.tie(0); cin.tie(0);
    cin>>n;
    f(i,1,n){
        int a,b,c;cin>>a>>b>>c;
        t[b][0]=t[c][0]=a;
        t[a][1]=b;
        t[a][2]=c;
    }
    
    int root=1;while(t[root][0])root=t[root][0];
    
    f(i,1,n)s[i][0]=n;
    calc(root,1);
    
    int lev=1,ans[2]{-1,-1};
    while(s[lev][1]){
        int tmp=s[lev][1]-s[lev][0];
        if(ans[1]<tmp)ans[0]=lev,ans[1]=tmp;
        ++lev;
    }
    cout<<ans[0]<<' '<<ans[1]+1;
    return 0;
}
 

문제 설명과 코드에 대한 피드백은 언제나 환영합니다.

 다양한 의견 댓글로 남겨주세요.