[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] << " ";

1 0 0 0 0
0 0 0 0 0fill_n(arr, n, true);:true初期化