[백준] 트리의 높이와 너비(2250)

문제 링크 : [백준] 트리의 높이와 너비(2250)

문제 설명

이진트리의 구조가 주어질 때, 너비가 제일 넓은 레벨과 그 너비를 출력하세요.
단, 트리는 아래와 같은 제약사항이 있습니다.

1. 같은 레벨에 있는 노드들은 같은 행에 존재합니다.
2. 한 열에는 노드 하나만 존재합니다.
3. 임의의 노드의 왼쪽 자식은 항상 부모 노드보다 왼쪽 열에 존재하고, 오른쪽 자식은 항상 부모 노드보다 오른쪽 열에 존재합니다.
4. 가장 왼쪽, 오른쪽 열의 양 옆은 비어있지 않습니다.

입력

N : 노드의 갯수(1<=n<=10,000)
p_i l_i r_i(p : 부모 노드의 번호, l : 왼쪽 자식 노드의 번호, r : 오른쪽 자식의 노드 번호)

19
1 2 3
2 4 5
3 6 7
4 8 -1
5 9 10
6 11 12
7 13 -1
8 -1 -1
9 14 15
10 -1 -1
11 16 -1
12 -1 -1
13 17 -1
14 -1 -1
15 18 -1
16 -1 -1
17 -1 19
18 -1 -1
19 -1 -1

출력

가장 넓은 레벨, 그 레벨의 너비

3 18

카테고리

#트리

시간 복잡도 상한

O(n²)까지 가능합니다.

해결 방법

1. 각 레벨의 너비를 알기 위해서는 아래의 내용을 파악해야 합니다.
   1-1. 각 노드의 레벨
   1-2. 각 노드의 열 번호
2. 각 노드의 레벨은 트리 순회를 통해 알 수 있습니다.(in, pre, post order 무관)
3. 각 노드의 열 번호를 알기 위해서는 자신의 노드의 왼쪽에 몇개의 노드가 있는지 파악해야 합니다.
4. 자신의 왼쪽에 있는 노드는 트리 순회를 하면서 아래와 같은 내용을 통해 알 수 있습니다.
   4-1. 임의의 노드 N_i의 위치는 부모의 위치(부모 노드의 왼쪽 노드 갯수 +1) + 자신의 왼쪽 자식의 노드 갯수가 됩니다.
   4-2. 부모의 위치는 자신의 왼쪽 자식 노드의 갯수 + 자신의 오른쪽 자식 노드의 갯수 + 1 이 됩니다.
5. post order로 4단계를 반복하며 각 노드의 레벨과 열 번호를 알아냅니다.
   5-1. 주의 할 점은 1번 노드가 항상 루트 노드가 아니기 때문에 루트 노드를 찾는 방법이 필요합니다.
   5-2. 입력을 받을 때, 자식 노드로 언급된 부분들을 체크하여, 나중에 자식 노드로 한번도 언급되지 않은 노드를 루트 노드로 찾게하였습니다.
6. 각 레벨별로 가장 왼쪽의 위치와 가장 오른쪽의 위치를 찾습니다.
7. 전체 레벨 중 너비가 가장 넓은 레벨을 찾아 출력합니다.

시간복잡도

O(n)

코드

#include<cstdio>
#include<algorithm>
using namespace std;
struct N{int l,r;}d[10001];
struct M{int l,r,h,o;}e[10001];
int n,i,x,y,f[10001][2],h,k,q[10001];
int r(int p,int h,int o){
    if(p<0)return 0;
    e[p].h=h;
    e[p].o=o;
    e[p].l=r(d[p].l,h+1,o)+1;
    e[p].r=r(d[p].r,h+1,o+e[p].l);
    return e[p].l+e[p].r;
}
int main(){
    scanf("%d",&n);
    for(i=0;i<n;i++){
        scanf("%d",&h);
        scanf("%d%d",&d[h].l,&d[h].r);
        q[d[h].l]++;
        q[d[h].r]++;
    }
    for(i=1;i<=n;i++){
        if(!q[i])r(i,1,0);
        f[i][0]=10001;
        f[i][1]=0;
    }
    for(i=1;i<=n;i++){
        h=e[i].h;k=e[i].l+e[i].o;
        f[h][0]=min(f[h][0],k);
        f[h][1]=max(f[h][1],k);
    }
    for(i=1;i<=n;i++){
        k=f[i][1]-f[i][0]+1;
        if(x<k)x=k,y=i;
    }
    printf("%d %d",y,x);
}