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

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

 

호호..

문제가 어려워 보이지만

차근차근 읽으보면

 

입력은 부모 -> 왼쪽자식 -> 오른쪽자식로 이루어진다

 

자식이 없는 곳은 -1 로 표현한다

 

[TREE] 백준 1991번 트리의 순회(C++)

[TREE] 백준 1991번 트리의 순회(C++)

사실 이 문제를 풀고온 후, 하나만 깨달으면 문제는 전혀 어렵지 않다.

 

이런 입력이 들어왔을 때

 

그림을 유심히 보자.

 

노드의 순서들이 어라.

 

"트리에서 왼쪽에 있는 것들이 먼저 번호가 매겨지네?"

 

어라...

 

"중위 순회"

 

무슨뜻이냐

 

노드에 위치가 정해지는 순서가 " 중위 순회 " 순서로 매겨지고 있다는 뜻이다.

 

앞선 그래프에서 중위순회로 탐색을 시작하게되면

8 4 2 14 9 18 15 5 10 1 16 11 6 12 3 17 19 13 7 인데

 

기가막히게 똑같네?

 

그렇다면 이제 우리가 비교해야되는것은

"너비"와"높이"

 

그것은 pos 재귀문을 지나가면서 depth를 하나식 늘려주면 되겠다~

 

position 및 그에따른 depth 이

앞선 입력 예제에 대해선 이렇게 나온다~

 

이제 여기까지 했으면 아마 나머지 부분은 푸는데 전혀 이상이 없을 것이다..

 

 

 

#include <iostream>

#include <vector>

#include <string>

using namespace std;

vector<int> v[10001];

int position[10001];

int arr[10001][2];

int p_p[10001] = {0};

int left_;

void pos(int temp, int depth);

int main()

{

    int n;

    cin >> n;

    left_ = 1;

    for (int i = 0; i < n; i++)

    {

        int parent, c1, c2;

        cin >> parent >> c1 >> c2;

        v[parent].push_back(c1);

        if (c1 != -1)

            p_p[c1] = parent;

        v[parent].push_back(c2);

        if (c2 != -1)

            p_p[c2] = parent;

    }

    int parr;

    for (int i = 1; i <= n; i++)

    {

        if (p_p[i] == 0)

        {

            parr = i;

            break;

        }

    }

    pos(parr, 1);

    // for (int i = 1; i <= n; i++)

    // {

    //     cout.width(3);

    //     cout << arr[i][0] << " ";

    // }

    // cout << "\n";

    // for (int i = 1; i <= n; i++)

    // {

    //     cout.width(3);

    //     cout << arr[i][1] << " ";

    // }

    // cout << "\n";

    int max_w = 1, sol_d = 1;

    for (int i = 1; i <= n - 1; i++)

        for (int j = i + 1; j <= n; j++)

            if (arr[i][1] == arr[j][1])

            {

                int t_w = abs(position[arr[i][0]] - position[arr[j][0]]);

                // cout << arr[i][0] << " 과 " << arr[j][0] << " 사이의 거리 : " << t_w+1 << "\n";

                if (t_w + 1 > max_w)

                {

                    max_w = t_w + 1;

                    sol_d = arr[i][1];

                }

                else if (t_w + 1 == max_w)

                {

                    if (sol_d >= arr[i][1])

                    {

                        sol_d = arr[i][1];

                        max_w = t_w + 1;

                    }

                }

            }

    cout << sol_d << " " << max_w;

}

void pos(int temp, int depth)

{

    int child = v[temp][0];

    if (!(child == -1)) // 왼쪽

        pos(child, depth + 1);

    arr[left_][0] = temp;

    position[temp] = left_;

    arr[left_][1] = depth;

    left_++;

    child = v[temp][1];

    if (!(child == -1)) // 오른쪽

        pos(child, depth + 1);

}

 

좀더 식을 깔끔히 할 수도 있을 것이다.!

int t_w = abs(position[arr[i][0]] - position[arr[j][0]]);

                // cout << arr[i][0] << " 과 " << arr[j][0] << " 사이의 거리 : " << t_w+1 << "\n";

               

왜냐면 이 부분은 그냥 첫번째 노드와 마지막 노드 사이의 거리만 계산하면 되지만

해당 방법은 모든 노드들간의 거리를 계산하기 때문이다.

 

해당 방법 해결을 위해선 위치를 arr[i][0]로 정해주는것이 아니라 해당 깊이에 따른 vector들을 정의하고 그 깊이에따른 vector를 포지션에 따라 저장한 후에 오름차순으로 정렬하고, 첫값과 끝값을 빼주면 될 것이다.

 

쨋든 끝!