[백준] 2250번 C/C++ 풀이 _ 트리의 높이와 너비

 

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

시간 제한메모리 제한제출정답맞은 사람정답 비율
2 초128 MB351497669527.043%

문제

이진트리를 다음의 규칙에 따라 행과 열에 번호가 붙어있는 격자 모양의 틀 속에 그리려고 한다. 이 때 다음의 규칙에 따라 그리려고 한다.

  1. 이진트리에서 같은 레벨(level)에 있는 노드는 같은 행에 위치한다.
  2. 한 열에는 한 노드만 존재한다.
  3. 임의의 노드의 왼쪽 부트리(left subtree)에 있는 노드들은 해당 노드보다 왼쪽의 열에 위치하고, 오른쪽 부트리(right subtree)에 있는 노드들은 해당 노드보다 오른쪽의 열에 위치한다.
  4. 노드가 배치된 가장 왼쪽 열과 오른쪽 열 사이엔 아무 노드도 없이 비어있는 열은 없다.

이와 같은 규칙에 따라 이진트리를 그릴 때 각 레벨의 너비는 그 레벨에 할당된 노드 중 가장 오른쪽에 위치한 노드의 열 번호에서 가장 왼쪽에 위치한 노드의 열 번호를 뺀 값 더하기 1로 정의한다. 트리의 레벨은 가장 위쪽에 있는 루트 노드가 1이고 아래로 1씩 증가한다.

아래 그림은 어떤 이진트리를 위의 규칙에 따라 그려 본 것이다. 첫 번째 레벨의 너비는 1, 두 번째 레벨의 너비는 13, 3번째, 4번째 레벨의 너비는 각각 18이고, 5번째 레벨의 너비는 13이며, 그리고 6번째 레벨의 너비는 12이다.

우리는 주어진 이진트리를 위의 규칙에 따라 그릴 때에 너비가 가장 넓은 레벨과 그 레벨의 너비를 계산하려고 한다. 위의 그림의 예에서 너비가 가장 넓은 레벨은 3번째와 4번째로 그 너비는 18이다. 너비가 가장 넓은 레벨이 두 개 이상 있을 때는 번호가 작은 레벨을 답으로 한다. 그러므로 이 예에 대한 답은 레벨은 3이고, 너비는 18이다.

임의의 이진트리가 입력으로 주어질 때 너비가 가장 넓은 레벨과 그 레벨의 너비를 출력하는 프로그램을 작성하시오

입력

첫째 줄에 노드의 개수를 나타내는 정수 N(1 ≤ N ≤ 10,000)이 주어진다. 다음 N개의 줄에는 각 줄마다 노드 번호와 해당 노드의 왼쪽 자식 노드와 오른쪽 자식 노드의 번호가 순서대로 주어진다. 노드들의 번호는 1부터 N까지이며, 자식이 없는 경우에는 자식 노드의 번호에 -1이 주어진다.

출력

첫째 줄에 너비가 가장 넓은 레벨과 그 레벨의 너비를 순서대로 출력한다. 너비가 가장 넓은 레벨이 두 개 이상 있을 때에는 번호가 작은 레벨을 출력한다.

예제 입력 1 

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

예제 출력 1 

3 18

출처

Olympiad 한국정보올림피아드 KOI 2003 고등부 1번

알고리즘 분류

풀이

이 문제에서 주의할 점은 "루트 노드는 1아닐 수 있다." 는 것입니다. 
문제에서 트리의 레벨은 가장 위쪽에 있는 루트 노드가 1이고 아래로 1씩 증가한다 라는 문장이 '루트가 1이다' 라는 착각을 주는데,
잘 읽어보면 가장 위쪽에 있는 루트 노드의 높이가 1이라는 말입니다다. 

루트 노드를 찾기 위해서 find_root 라는 함수를 만들었습니다. 
노드를 갱신할 때, node_parent_vec 에서 부모 노드를 가리키는 벡터를 생성했습니다.
부모 노드를 가리키는 벡터가 있는 경우에 find_root 는 더 이상 가리키는 게 없는 노드를 만났을 때, 그 노드를 부모로 여기면 됩니다. 

이 문제의 주요 풀이 방법은 bfs로 높이 갱신 + 중위 순회로 col 값 갱신을 하는 것입니다.  


문제에서의 특징을 살펴보면 서브트리의 루트노드를 기준으로
좌측 서브트리는 루트노드의 왼쪽
우측 서브트리는 루트노드의 오른쪽
에 있는 것을 확인할 수 있습니다.
이는 중위순회를 통하여 쉽게 구할 수 있습니다. 

bfs를 통해서는 동일한 높이를 가진 노드들을 체크해줍니다. 

그리고 마지막에 sort() 함수에서 높이 순서대로 정렬하고 높이가 같은 경우에는 col 순서대로 정렬합니다.
그리고 높이가 같은 경우에 col 의 최대값을 구하고 갱신합니다. 

자세한 내용은 소스코드를 참조하면 될 것 같습니다. 

소스코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
#include <iostream>
#include <vector> 
#include <queue>
#include <algorithm>
using namespace std;
 
// global
typedef struct NODE {
    int val;
    int left;
    int right;
    int height;
    int col;
}NODE;
vector<NODE> node_vec;
vector<int> node_parent_vec;
int col_idx = 1;
 
// 중위순회를 통하여 col 값을 갱신 
void inorder(int _this_node_idx) {
    NODE* this_node = &node_vec.at(_this_node_idx);
    if (this_node->left != -1) inorder(this_node->left);
    this_node->col = col_idx++;    
    if (this_node->right != -1) inorder(this_node->right);
}
 
// bfs 를 통하여 높이를 갱신
void bfs(int _start_node) {
    queue<int> bfs_queue;
    bfs_queue.push(_start_node);
    int bfs_size = bfs_queue.size();
    int height = 1;
    while (bfs_size) {
        int this_node_idx = bfs_queue.front();    
        bfs_queue.pop();
        bfs_size--;
 
        NODE* this_node = &node_vec.at(this_node_idx); 
        this_node->height = height;
        if (this_node->left != -1) bfs_queue.push(this_node->left);
        if (this_node->right != -1) bfs_queue.push(this_node->right);
 
        if (bfs_size == 0) {
            height++;
            bfs_size = bfs_queue.size();
        } 
    } 
}
 
// node를 높이에 맞춰서 정렬하고, 높이가 같으면 col 값에 따라서 정렬한다. 
int sort_node(const NODE& _node_1, const NODE& _node_2) {
    if (_node_1.height != _node_2.height)
        return _node_1.height < _node_2.height; 
    else 
        return _node_1.col < _node_2.col;
}
 
int find_root() {
    int root = 1;
    // 부모가 없을 때 까지 갱신 
    while (node_parent_vec.at(root) != -1)
        root = node_parent_vec.at(root);
 
    return root;
}
 
int main() {
    ios::sync_with_stdio(false);
    int N;
    cin >> N;
    node_vec.resize(N+1);
    node_parent_vec.resize(N+1-1);
    for (int n_idx = 1; n_idx <= N; n_idx++){
        int this_node, left, right;
        cin >> this_node >> left >> right;
        node_vec.at(this_node).left = left;
        node_vec.at(this_node).right = right;
        node_vec.at(this_node).height = node_vec.at(this_node).col = -1;
 
        // 부모 노드 모두 표시 
        if (left != -1)  node_parent_vec.at(left) = this_node;
        if (right != -1)  node_parent_vec.at(right) = this_node;
    }
 
    // 루트 찾기 
    int root = find_root();
 
    // 중위순회로 각각의 col 위치를 갱신한다. 
    inorder(root);
 
    // bfs 로 각각의 높이를 갱신한다. 
    bfs(root);
 
    // 각각의 높이에 해당하는 원소들의 col 위치를 통하여 최대 넓이를 구한다. 
    sort(node_vec.begin()+1, node_vec.end(), sort_node);
 
    // 컬럼 차이의 최대 값을 구한다 
    int answer_width = 1;
    int answer_height = 1;
    int height = 1;
    int row_first = -1;
    for (int n_idx = 2; n_idx <= N; n_idx++) {
        if (height < node_vec.at(n_idx).height) {
            height++;
            row_first = n_idx;
        }
        else if (height == node_vec.at(n_idx).height) {
            if (answer_width < node_vec.at(n_idx).col - node_vec.at(row_first).col + 1){
                answer_width = node_vec.at(n_idx).col - node_vec.at(row_first).col + 1;
                answer_height = height;
            }
        } 
    }
    cout << answer_height << " " << answer_width;
 
    return 0
}
cs