[C/C++] 백준 #2250 트리의 높이와 너비(이진 탐색 트리)

#2250 문제는 이진 탐색 트리를 잘 이해하는 가에 대한 문제입니다.

 

문제의 링크입니다.

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

2250번: 트리의 높이와 너비

이진 탐색 트리(BST; Binary Search Tree)는 노드들을 탐색하는 방법으로 3가지 방법을 사용합니다.  전위(pre-order), 중위(in-order), 후위(post-order) 탐색법입니다.  우리는 이 중에 중위 탐색법을 사용합니다.

 

Binary Search Tree

위와 같은 이진 탐색 트리가 있다면, 왼쪽부터 오른쪽까지 배열을 하기 위해서는 중위 탐색을 이용해서 숫자를 잡아주어야 합니다.  그러면 노란색 글자와 같이 제일 왼쪽에 있는 트리부터 제일 오른쪽까지 배열을 할 수 있습니다.  이진 탐색 트리를 크기값에 따라서 왼쪽 서브트리는 현재 노드값보다 작은 것들을 놓고, 오른쪽 서브트리는 현재 노드값보다 큰 것들을 놓는다면, 중위 탐색법으로 정렬된 결과를 얻을 수 있습니다.

 

문제에서 요구하는 것은 레벨에서의 너비입니다.  그래서 루트 노드에서부터 얼마나 멀리 떨어져있는지도 같이 계산을 해주어야 합니다.  저는 배열을 이용해서 제일 왼쪽의 노드값과 제일 오른쪽의 노드값을 저장하게 했습니다.  이러면 자연스럽게 깊이값에 따른 너비를 쉽게 계산할 수 있습니다.

 

제가 작성한 소스입니다.

//------------------------------------------------
//    baekjoon #2250 - Tree's Height and Width
//        - by Aubrey Choi
//        - created at 2019-07-24
//------------------------------------------------
#include <stdio.h>

struct Node { int p, l, r; } node[10001];
int d[10001][2], maxd, order = 1;
void trav(int r, int k)
{
    if(r == -1) return;
    trav(node[r].l, k+1);
    if(d[k][0] == 0)
    {
        d[k][0] = d[k][1] = order;
        if(maxd < k) maxd = k;
    }
    else
    {
        if(d[k][0] > order) d[k][0] = order;
        else if(d[k][1] < order) d[k][1] = order;
    }
    order++;
    trav(node[r].r, k+1);
}

int main()
{
    int n, r;
    scanf("%d", &n);
    while(n--)
    {
        int n, l, r;
        scanf("%d%d%d", &n, &l, &r);
        node[n].l = l, node[n].r = r;
        if(l!=-1) node[l].p = n;
        if(r!=-1) node[r].p = n;
    }
    for(r = 1; node[r].p; r = node[r].p) ;
    trav(r, 1);
    int max = -1, k;
    for(int i = 1; i <= maxd; i++)
        if(d[i][1]-d[i][0] > max) max = d[i][1]-d[i][0], k = i;
    printf("%d %d\n", k, max+1);
}