[백준] 2250 :: 트리의 높이와 넓이

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

2250번: 트리의 높이와 너비

 

문제 그대로 트리의 넓이를 구하는 문제이다.

가장 중요한 포인트는 트리의 각 노드가 몇번째 열에 위치하는지를 알아내는 것인데, 조금만 고민해보면 이것은 preorder 트래버설로 알아낼 수 있다.

프리오더 트래버설은 왼쪽 -> 루트 -> 오른쪽 이렇게 탐색하는 방식이고 이 순서대로 탐색하면서 번호를 매기면, 그 번호가 열 번호가 되게 된다

문제 예시로 보면 1번 열부터 19번열까지 8 -> 4 -> 2-> 14 -> 9 -> /..... 이런식으로 되는 것이다.

 

프리오더 탐색을하면서 depth마다 각 열넘버를 저장하고, 그 후에 n까지 depth를 탐색하며 가장 작은 열 번호와 가장 큰 열 번호의 차이에다가 +1을 해주면 너비가 된다.

 

 

아맞다, 단 루트가 항상 1이 아님을 주의해야한다.

이것때매 틀렸다..

 

 

소스코드

 

#include <iostream>
#include <vector>
using namespace std;
 
int n;
pair<int, int> tree[10001];//트리정보 저장, 왼쪽 자식노드, 오른쪽 자식노드
vector<int> v[10001];
int par[10001];
int cnt = 1;
void preorder(int node, int depth) { 
    if (tree[node].first != -1)
        preorder(tree[node].first, depth+1);
    v[depth].push_back(cnt);
    cnt++;
    if (tree[node].second != -1)
        preorder(tree[node].second, depth + 1);
}
 
int main() {
    cin >> n;
    for (int i = 0; i < n; i++) {
        int a, b, c;
        cin >> a >> b >> c;
        tree[a] = { b,c };
        par[b] = a;
        par[c] = a;
    }
    int root;
    for (int i = 1; i <= n; i++) {
        if (par[i] == 0) {
            root = i;
            break;
        }
    }
    preorder(root, 1);
    int level = 0;
    int ans = -1;
 
    for (int i = 1; i <= n; i++) {
        if (v[i].size() == 0) continue;
        int length = v[i][v[i].size() - 1] - v[i][0] + 1;
        if (ans < length) {
            ans = length;
            level = i;
        }
    }
    cout << level << " " << ans << endl;
}