출처 : https://www.acmicpc.net/problem/2250
트리의 높이와 너비 성공
| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞은 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 2 초 | 128 MB | 3514 | 976 | 695 | 27.043% |
문제
이진트리를 다음의 규칙에 따라 행과 열에 번호가 붙어있는 격자 모양의 틀 속에 그리려고 한다. 이 때 다음의 규칙에 따라 그리려고 한다.
- 이진트리에서 같은 레벨(level)에 있는 노드는 같은 행에 위치한다.
- 한 열에는 한 노드만 존재한다.
- 임의의 노드의 왼쪽 부트리(left subtree)에 있는 노드들은 해당 노드보다 왼쪽의 열에 위치하고, 오른쪽 부트리(right subtree)에 있는 노드들은 해당 노드보다 오른쪽의 열에 위치한다.
- 노드가 배치된 가장 왼쪽 열과 오른쪽 열 사이엔 아무 노드도 없이 비어있는 열은 없다.
이와 같은 규칙에 따라 이진트리를 그릴 때 각 레벨의 너비는 그 레벨에 할당된 노드 중 가장 오른쪽에 위치한 노드의 열 번호에서 가장 왼쪽에 위치한 노드의 열 번호를 뺀 값 더하기 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
풀이
이 문제에서 주의할 점은 "루트 노드는 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 |