[BOJ/伯俊]2250(木の高さと幅)C++
テーマ
ツリー/ツリー巡回/inorder(中位数巡回)/DFS
boj2250
どうやって木を実現するか悩んだ.
最初は構造体に近づき、シャベルで掘って、ブーブー
バイナリツリーなので2次元配列解でも十分だと思います!!
中尉の巡回解答に時間がかかったことに気づく…!
boj 1991(ツリー巡り)を参照してください.
//よく見ると、col値は中位数の順序と同じです.
ソースコード
ソース1
/*
boj2250.cpp
2021-01-08
트리의 높이와 너비
*/
#include <bits/stdc++.h>
using namespace std;
int tree[10001][2] = { 0, };
bool rootNode[10001];
int col = 0;
int row = 0;
vector <int> loc[10001];
vector <pair<int,int>> len;
bool cmp(const pair<int, int>& a, const pair<int, int>& b)
{
return a.second > b.second;
}
void inorder(int k, int row) {
if (k == -1) return;
inorder(tree[k][0],row+1);
col++;
loc[row].push_back(col);
inorder(tree[k][1],row+1);
}
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
int n; cin >> n;
fill_n(rootNode, n + 1, true);
for (int i = 0; i < n; i++) {
int root, left, right; cin >> root >> left >> right;
tree[root][0] = left; tree[root][1] = right;
if(left != -1)
rootNode[left] = false;
if(right != -1)
rootNode[right] = false;
}
int root = 0;
for (int i = 1; i <= n; i++) {
if (rootNode[i]) {
root = i;
break;
}
}
inorder(root, 1);
int row = 1;
while (loc[row].size()) {
int min = loc[row][0];
int max = loc[row][loc[row].size() - 1];
len.push_back({ row,max - min + 1 });
row++;
}
sort(len.begin(), len.end(),cmp);
cout << len[0].first << " " << len[0].second;
}
ソース2
queue使用->[編集]vectorでもfront/back...!
[STL]ベクトル整理と例を参照してください.
vector pairを外してfor文を返して、その時に正しい答えを更新します
/*
boj2250.cpp
2021-01-08 정설희
트리의 높이와 너비
*/
#include <bits/stdc++.h>
using namespace std;
int tree[10001][2] = { 0, };
bool rootNode[10001];
int col = 0;
int row = 0;
queue <int> q[10001];
void inorder(int k, int row) {
if (k == -1) return;
inorder(tree[k][0],row+1);
col++;
q[row].push(col);
inorder(tree[k][1],row+1);
}
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
int n; cin >> n;
fill_n(rootNode, n + 1, true);
for (int i = 0; i < n; i++) {
int root, left, right; cin >> root >> left >> right;
tree[root][0] = left; tree[root][1] = right;
if(left != -1)
rootNode[left] = false;
if(right != -1)
rootNode[right] = false;
}
int root = 0;
for (int i = 1; i <= n; i++) {
if (rootNode[i]) {
root = i;
break;
}
}
inorder(root, 1);
int ans1 = 1;
int ans2 = q[1].front()-q[1].back()+1;
int row = 2;
while (!q[row].empty()) {
int min = q[row].front();
int max = q[row].back();
int tmp = max - min + 1;
if (tmp > ans2) {
ans1 = row; ans2 = tmp;
}
row++;
}
cout << ans1 << " " << ans2;
}
学識
ツリー->DFS/BFS/巡回
ツリーの問題を解くときは、必ずDFS/BFS/サイクルを考えてください.
ベクトル対メソッド
vector<pair<int,int>>v;
ソフトウェアメソッド<:昇順
>:降順
sort(v.begin(),v.end(),cmp)
第一基準bool cmp(const pair<int, int> &a, const pair<int, int> &b)
{
return a.first < b.first;
}
第2基準bool cmp(const pair<int, int> &a, const pair<int, int> &b)
{
return a.second < b.second;
}
bool arr初期化方法
bool arr[5] = {false};
:false初期化->このメソッドはtrueに初期化できません.
bool arr1[5] = { true };
bool arr2[5] = { false };
for (int i = 0; i < 5; i++)
cout << arr1[i] << " ";
cout << "\n";
for (int i = 0; i < 5; i++)
cout << arr2[i] << " ";
Reference
この問題について([BOJ/伯俊]2250(木の高さと幅)C++), 我々は、より多くの情報をここで見つけました https://velog.io/@xxeol/BOJ백준-2250-트리의-높이와-너비-Cテキストは自由に共有またはコピーできます。ただし、このドキュメントのURLは参考URLとして残しておいてください。
Collection and Share based on the CC Protocol