[BOJ/백준] 2250 (트리의 높이와 너비) C++

·2021년 1월 8일
0

boj

목록 보기
2/5

주제

트리 / 트리 순회 / inorder(중위순회) / DFS

boj2250

트리를 어떻게 구현해야할지 고민했다..
처음엔 구조체로 접근했다가 삽질하다가 ㅠㅠ
이진트리니까 이차원배열로 풀어도 충분하다고 생각!!

중위순회로 푸는 문제임을 깨닫는데 시간이 걸렸다..!
boj1991(트리순회) 참고!

// 자세히 보면 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 사용 -> [edited] vector 에도 front / back이 있다고 한다..!
[STL] vector 벡터 정리 및 예제 참고!
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 소트 방법

vector<pair<int,int>>v; 소트 방법

< : 오름차순
> : 내림차순

sort(v.begin(),v.end(),cmp)

first 기준

bool cmp(const pair<int, int> &a, const pair<int, int> &b)
{
    return a.first < b.first;
}

second 기준

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로 초기화 할 수 없다.

<input>

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

<output>
1 0 0 0 0
0 0 0 0 0

fill_n(arr, n, true); : true로 초기화

0개의 댓글