[도전 16일차] 트리의 높이와 너비 - KOI 고등부 풀이

KOI 고등부 풀이

※복습 : 

문제 : 백준 2250 트리의 높이와 너비

문제 링크

 

사용 알고리즘 : 트리 순회

 

풀이:

출처 : 백준

기본적인 규칙은 모든 노드에 대하여 자신의 왼쪽 서브트리에 있는 노드들은 열번호가 작고, 오른쪽 서브트리에 있는 노드들은 열번호가 크다.

 

가장 먼저 관찰할 수 있는 사실은 루트에서 왼쪽으로 쭉 쭉 내려왔을 때 끝에 있는 노드가 열번호 1번을 차지한다. 같은 맥락으로 1번의 부모가 2번을 차지하고, 오른쪽 자식이 있을 때까지 올라간다. 오른쪽 자식이 있으면 오른쪽 자식으로 내려가서 다시 가장 왼쪽 자식을 찾아서 넘버링한다. 이 시행을 반복하면 모든 노드에 대해 열번호 넘버링이 끝난다.

 

결론 : 반복적 중위 순회 (Iterative Inorder Traversal) 와 규칙이 일치한다.

 

위에서 언급한대로 반복문을 돌려도 되고, 재귀함수로 중위 순회를 시행해도 된다. 트리의 중위 순회는 기초 알고리즘이기 때문에 코드업을 통해 연습하자.

 

이번에는 반복문과 스택을 이용해 중위 순회를 구현하겠다.

열번호 넘버링을 해준 후 루트 노드에서 레벨링 순회(BFS) 를 돌려서 각각의 레벨에 대해 가장 왼쪽 노드와 오른쪽노드의 열번호 차이를 구해, 최대값을 갱신해 주면 된다.

코드

//pentagon@sasa.hs.kr 
#include<bits/stdc++.h>
#define ll long long
#define vsort(v) sort(v.begin(),v.end())
const int INF = 1e9;
using namespace std;
struct node{
    int root,left,right;
    int col;
    node():left(-1),right(-1),root(0){}
};
node tree[10010];
int n,ans_lvl,ans,num;
void iter_inorder(int s){
    stack<int> st;
    while(1){
        for(;s!=-1;){
            st.push(s);
            s=tree[s].left;
        }
        if(st.empty()) break;
        s=st.top(); st.pop();
        tree[s].col=++num;
        s=tree[s].right;
    }
}
void iter_levelorder(int s,int lvl){
    queue<pair<int,int>> q;
    q.push({s,lvl});
    int L=0;
    while(!q.empty()){
        s=q.front().first;
        lvl=q.front().second; q.pop();
        if(tree[s].left!=-1)
            q.push({tree[s].left,lvl+1});
        if(tree[s].right!=-1)
            q.push({tree[s].right,lvl+1});
        if(!L) L=tree[s].col;
        if(q.empty() || q.front().second > lvl){
            if((tree[s].col - L + 1) > ans){
                ans_lvl=lvl;
                ans=(tree[s].col - L + 1);
            }
            L=0;
        }
    }
}
int main(){
    ios::sync_with_stdio(false);cin.tie(0);
    cin>>n;
    for(int i=1,a,b,c;i<=n;i++){
        cin>>a>>b>>c;
        tree[a].left=b; tree[a].right=c;
        if(b!=-1) tree[b].root=a;
        if(c!=-1) tree[c].root=a;
    }
    int s=1;
    while(tree[s].root>0) s=tree[s].root;
    iter_inorder(s);
    iter_levelorder(s,1);
    cout<<ans_lvl<<' '<<ans;
}

 

궁금한 점이 있으시다면 질문 남겨주세요 :)