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

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

2250번: 트리의 높이와 너비

 

전체 코드

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
pair<int, int> node[10001];
vector<int> v[10001];
int column[10001];
int parent[10001];
int col = 1;
int h = 1;
int mh = 1;
void inorder(int root)
{
    mh = max(mh, h);

    if (node[root].first != -1) {
        h++;
        inorder(node[root].first);
        h--;
    }

    column[root] = col++;
    v[h].push_back(col);

    if (node[root].second != -1) {
        h++;
        inorder(node[root].second);
        h--;
    }
}

int rootFind()
{
    int cur = 1;

    while (parent[cur] != -1)
    {
        cur = parent[cur];
    }

    return cur;
}
int main(void)
{

    int N = 0;
    cin >> N;
    fill(parent, parent + N + 1, -1);

    for (int i = 0; i < N; i++)
    {
        int n, left, right;
        cin >> n >> left >> right;
        node[n].first = left;
        node[n].second = right;

        if (left != -1)
            parent[left] = n;
        if (right != -1)
            parent[right] = n;
    }

    int root = rootFind();
    inorder(root);

    int resLevel = 1;
    int resWidth = 1;
    for (int i = 1; i <= mh; i++)
    {
        sort(v[i].begin(), v[i].end());
        if (!v[i].empty() && resWidth < v[i][v[i].size() - 1] - v[i][0] + 1)
        {
            resWidth = v[i][v[i].size() - 1] - v[i][0] + 1;
            resLevel = i;
        }
    }
    cout << resLevel << " " << resWidth;
}

 

변수

pair<int, int> node[10001];
vector<int> v[10001];
int column[10001];
int parent[10001];
int col = 1;
int h = 1;
int mh = 1;

pair<int,int> node[i] :  노드 번호 i의 left 노드의 번호와 right 번호를 저장 ( first(left), second(right) )

vector<int> v[h] :  높이가 h인 노드의 열번호(col)를 저장

column[i] : 노드 번호 i의 열번호(col)를 저장

parent[i] : 노드 번호 i의 부모 정보를 저장

int col = 1 : 현재 col 정보

int h = 1 : 현재 높이 정보

int mh : 트리의 최대 높이 정보를 저장

 

main함수

    int N = 0;
    cin >> N;
    fill(parent, parent + N + 1, -1);

    for (int i = 0; i < N; i++)
    {
        int n, left, right;
        cin >> n >> left >> right;
        node[n].first = left;
        node[n].second = right;

        if (left != -1)
            parent[left] = n;
        if (right != -1)
            parent[right] = n;
    }

parent를 -1로 초기화 시키고

각 노드의 left와 right 그리고 부모의 정보를 저장해줍니다.

 

int root = rootFind();
inorder(root);

int root에 루트 노드의 번호를 담습니다.

inorder(중위 순회)를 통해서 col 정보와 노드들의 높이도 찾고, 각 높이별 col 정보도 저장할 겁니다.

 

 int resLevel = 1;
 int resWidth = 1;
for (int i = 1; i <= mh; i++)
{
        sort(v[i].begin(), v[i].end());
        if (!v[i].empty() && resWidth < v[i][v[i].size() - 1] - v[i][0] + 1)
        {
            resWidth = v[i][v[i].size() - 1] - v[i][0] + 1;
            resLevel = i;
        }
}
cout << resLevel << " " << resWidth;

일단 N이 1 이상으로 입력이 들어오므로 무조건 최소한 결과의 높이는 1이고 너비는 1입니다.

높이 1부터 최대 높이(mh)까지

각 높이 별로 최대 너비를 계산해 갱신해줍니다.

v[i]에는 높이가 i인 col들이 저장되어 있으니 이것을 오름차순으로 정렬해

가장 큰 col과 가장 작은 col을 빼고 +1을해 너비를 구합니다.

만약 이 너비가 현재 결과 너비인 resWidth보다 크다면 갱신해줍니다.

i는 1부터 mh까지 갱신해 나가니 너비가 같다면 갱신이 안되니 번호가 작은 레벨을 기준으로 찾을 수 있지요.

 

rootFind() 함수

int rootFind()
{
    int cur = 1;

    while (parent[cur] != -1)
    {
        cur = parent[cur];
    }

    return cur;
}

N은 1이상이므로 노드 1은 무조건 존재한다.

이 노드를 기준으로 부모를 타고타고 올라가 루트를 찾을 수 있다.

 

중위순회 함수

void inorder(int root)
{
    mh = max(mh, h);

    if (node[root].first != -1) {
        h++;
        inorder(node[root].first);
        h--;
    }

    column[root] = col++;
    v[h].push_back(col);

    if (node[root].second != -1) {
        h++;
        inorder(node[root].second);
        h--;
    }
}

현재 h가 mh보다 클 경우 갱신해준다.

현재 노드의 left가 -1이 아니라면 왼쪽 자식이 있으므로 들어간다.

이때 높이는 증가하므로 h++해준다.

그리고 함수를 빠져나올 땐 높이가 다시 원상 복귀되니 h--를 해주자.

그리고 노드의 column 정보는 잘 보면 중위 순회 탐색할 때 root가 된다.

그리고 이 column 정보는 높이가 h일 때 갱신된 거이니

v[h]에 col 정보를 넣어주자.

 

 

마지막으로 결괏값 출력

cout << resLevel << " " << resWidth;