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

문제 링크: https://www.acmicpc.net/problem/2250

2250번: 트리의 높이와 너비

<문제 풀이> 트리

트리의 루트를 기준으로 왼쪽 서브 트리, 오른쪽 서브 트리를 각각 중위 순회하면 노드들의 열 번호를 알 수 있습니다.

왼쪽 서브트리를 중위 순회한 결과는 (8, 4, 2, 14, 9, 18, 15, 5, 10)
오른쪽 서브트리를 중위 순회한 결과는 (16, 11, 6, 12, 3, 17, 19, 13, 7)

그러면 벡터에 다음을 4가지를 push 하면 인덱스로 트리에서 각 정점의 열 번호를 알 수 있습니다.

 

1. 인덱스를 1부터 사용하기위해 0 push

2. 루트의 왼쪽 서브트리 중위 순회 결과 push

3. 루트 push

4. 루트의 오른쪽 서브트리 중위 순회 결과 push

 

vector = (0, 8, 4, 2, 14, 9, 18, 15, 5, 10, 1, 16, 11, 6, 12, 3, 17, 19, 13, 7)

 

그리고 이제 bfs로 레벨 순회를 해서 각 정점의 레벨을 알아낸 뒤 레벨별로 너비의 최댓값을 구하면 됩니다.

 

<C++ 소스 코드>

#include <iostream>
#include <algorithm>
#include <queue>
#include <vector>
using namespace std;
 
int n;
int lc[10001];
int rc[10001];
int level[10001];
bool isRoot[10001];
vector<int> col;
 
 
int getRoot() {
    for (int i = 1; i <= n; i++) {
        if (lc[i] != -1) isRoot[lc[i]] = false;
        if (rc[i] != -1) isRoot[rc[i]] = false;
    }
    for (int i = 1; i <= n; i++) if (isRoot[i]) return i;
}
 
/*레벨 순회*/
void bfs(int root) {
    queue<int> q;
    q.push(root);
    level[root] = 1;
    while (!q.empty()) {
        int cur = q.front();
        q.pop();
        if (lc[cur] != -1) {
            q.push(lc[cur]);
            level[lc[cur]] = level[cur] + 1;
        };
        if (rc[cur] != -1) {
            q.push(rc[cur]);
            level[rc[cur]] = level[cur] + 1;
        }
    }
}
 
/*중위 순회*/
void inorder(int root) {
    if (lc[root] != -1) inorder(lc[root]);
    col.push_back(root);
    if (rc[root] != -1)inorder(rc[root]);
}
 
int main(void) {
    ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
 
    cin >> n;
 
    fill(lc, lc + 10001, -1);
    fill(rc, rc + 10001, -1);
 
    for (int i = 0; i < n; i++) {
        int v, l, r;
        cin >> v >> l >> r;
        lc[v] = l;
        rc[v] = r;
        isRoot[v] = true; //처음엔 모든 정점을 root로 가정
    }
 
 
    int root = getRoot();
    bfs(root); // 레벨 순회
    col.push_back(0); // 열 인덱스를 1부터 사용하기 위함
    if (lc[root] != -1) inorder(lc[root]); // 루트의 왼쪽 노드 col 벡터에 추가
    col.push_back(root); // root 노드 col 벡터에 추가
    if (rc[root] != -1) inorder(rc[root]); // 루트의 오른쪽 노드 col 백터에 추가
 
    int size = col.size();
    int width = 0;
    int min_level = 10000;
 
    for (int s = 1; s < size; s++) {
        for (int e = size - 1; e >= s; e--) {
            if (level[col[s]] == level[col[e]]) {
                if (e - s + 1 == width) {
                    width = e - s + 1;
                    min_level = min(min_level, level[col[s]]);
                }
                else if (e - s + 1 > width) {
                    min_level = level[col[s]];
                    width = e - s + 1;
                }
                break;
            }
        }
    }
 
    cout << min_level << " " << width;
    return 0;
}