백준 2250 - 트리의 높이와 너비 (C++)

 

 
규칙에 맞게 트리를 구성한 뒤, 트리에서 가장 긴 너비와 해당 너비의 레벨을 출력하면 된다.
 

문제 풀이

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

 
위의 입력을 기준으로 이해해보자.
 

 
트리는 위 그림과 같이 구성될 것이다.
여기서, 우리가 구해야 하는 것은, 특정 레벨에서의 너비이다.
 
너비를 구하는 법은 우측에 있는 노드의 위치에서 좌측에 있는 노드의 위치를 빼고 1을 더하는 것이다.
그렇다면, 각 노드의 위치를 구하는 것이 먼저일 것이다.
 
위치는 어떻게 구해야 할까?
 
문제의 규칙중에, 특정 노드의 왼쪽 서브트리는  노드보다 왼쪽에 위치하며, 오른쪽 서브트리는 노드보다 오른쪽에 위치한다는 조건이 있다.

그림에서 볼 수 있듯이, 왼쪽 서브트리의 모든 노드는 나보다 왼쪽에 있으며, 오른쪽 서브트리의 모든 노드는 나보다 우측에 있다.
 
또한, 모든 열에는 하나의 노드만 존재한다는 조건도 있는데 이 조건까지 합치게 되면, 하나의 규칙을 발견할 수 있다.
 
어떤 노드의 위치는 왼쪽에 있는 노드의 개수 + 1이 된다는 것이다.

1번 노드의 왼쪽에는 9개의 노드가 존재한다.
그러므로, 1번 노드의 위치는 10이 된다.
 
그렇다면, 특정 노드의 위치를 구하기 위해선 왼쪽에 있는 노드의 개수를 구해야 한다는 것이다.
 
왼쪽에 있는 노드의 개수를 어떻게 구해야 할까?
왼쪽 서브트리의 노드 개수를 구하면 된다. 우리는 BFS든 DFS든 탐색 알고리즘을 이용하여, 특정 트리의 노드 개수를 구할 수 있다.
 
왼쪽 서브트리의 루트 노드를 기준으로 BFS든 DFS든 실행하게 되면, 노드의 개수를 구할 수 있을 것이다.
하지만, 왼쪽 서브트리만 구한다고 해서 왼쪽에 있는 모든 노드의 개수를 구할 수는 없다. 

3번 노드를 기준으로 보자.
왼쪽 서브트리의 노드 개수는 총 4개이다.
 
하지만, 실제로 전체 트리에서 3번 노드보다 왼쪽에 있는 노드는 위의 그림에서 파란색 원으로 감싸고 있는 만큼이다.
총 14개가 존재한다.
 
즉, 서브트리의 개수만 구하게 되면 특정 노드에선 반례가 존재할 수 있다는 것이다.
그러므로, 서브트리의 개수와 함께 고려해야 하는 것이 하나 있다.
 
바로, 부모 노드의 위치이다.
 
특정 노드의 왼쪽 서브트리는 해당 노드보다 왼쪽에 위치하며, 오른쪽 서브트리는 해당 노드보다 오른쪽에 위치한다.
노드가 없이 비어있는 열은 없다.
 
위의 조건들을 깊게 생각해보자.
왼쪽 서브트리의 모든 노드는 나보다 왼쪽에 위치하고, 오른쪽 서브트리의 모든 노드는 나보다 오른쪽에 위치한다.
또한, 그 사이에 공백이 존재하지도 않는다.
 
그렇다면, 나의 위치는 왼쪽 서브트리중 가장 오른쪽에 있는 노드보다 1만큼 크며, 오른쪽 서브트리중 가장 왼쪽에 있는 노드보다 1만큼 작다고 할 수 있을 것이다. 
 
이를 바꿔말하면, 특정 노드에서 왼쪽 서브트리중 가장 왼쪽에 있는 노드는 특정 노드의 부모노드의 위치 + 1 이라고도 표현할 수 있을 것이다.

 
그림에서 알 수 있듯이, 3번 노드를 기준으로 보았을 때 왼쪽 서브트리중 가장 왼쪽에 있는 노드(16번 노드)는 3번 노드의 부모노드 (1번 노드)보다 1만큼 큰 위치값을 가지고 있다.
 
3번 노드에서 16번 위치 값을 빼면, 나오는 값은 3번 노드와 16번 노드 사이에 있는 노드 개수 + 1이 나올 것이다.
=> 3번노드 위치 - 16번노드 위치 = 3번과 16번 사이 노드의 개수 + 1 = 왼쪽 서브트리의 노드 개수
 
앞에서, 16번 노드의 위치는 1번 노드의 위치 + 1이라고 하였으므로, 식을 다시 아래와 같이 정리할 수 있을 것이다.
=> 3번 노드 위치 - 1번 노드의 위치 - 1 = 왼쪽 서브트리의 노드 개수
=> 3번 노드 위치 = 1번 노드의 위치 + 왼쪽 서브트리의 노드 개수 + 1
 
그렇다면, 모든 노드에 대해 부모 노드의 위치 + 왼쪽 서브트리의 노드 개수 + 1이라는 공식을 사용해도 될까?
역시나 안된다.
 
위의 그림에서 2번 노드를 보자.
2번 노드의 부모노드의 위치는 10이며, 왼쪽 서브트리의 노드 개수는 2개이다.
그렇다면 2번 노드의 위치가 13이어야 하는데, 실제로는 3이다.
 
그러므로, 2번 노드의 경우엔 다른 방법으로 위치를 구해야 한다.
어렵지 않다. 위에서 생각했던 것과 동일한 논리로 생각해보면, 부모의 위치 - 우측 서브트리의 노드 개수 - 1이 나의 위치가 된다.
 
이를 정리해보자.
 
내가 부모 노드의 왼쪽에 있다면, 나의 위치는 부모의 위치 - 우측 서브트리의 노드 개수 - 1 이다.
내가 부모 노드의 오른쪽에 있다면, 나의 위치는 부모의 위치 + 좌측 서브트리의 노드 개수 + 1 이다.
 
이 공식을 이용하여, 모든 노드의 위치를 구할 수 있고, 모든 노드의 위치를 구했다면 모든 레벨에 대해 너비의 최소, 최대 또한 구할 수 있게 된다.
 

코드 풀이

struct Node
{
    int Level = 0;
    int Position = 0;
    
    int Parent = -1;
    int LeftChild = 0;
    int RightChild = 0;
};

 
먼저, 노드의 구조체를 선언하였다.
노드에는 레벨과 위치, 부모의 인덱스, 왼쪽 자식의 인덱스, 오른쪽 자식의 인덱스 정보가 담겨있다.
 
부모의 인덱스는 처음에 -1로 초기화해주었는데, 이는 루트노드를 구별하기 위해서이다.
뒤에서 모든 자식 노드의 부모노드를 갱신해줄 것인데, 루트노드의 경우엔 부모노드가 없으므로 값이 갱신되지 않아 -1의 값을 보유하게 된다. 이 값으로 루트노드를 판별할 것이다.
 

int NumNode = 0;
std::cin >> NumNode;

std::vector<Node> Nodes(NumNode + 1);
for (int i = 1; i <= NumNode; i++)
{
    int Index = 0;
    int LeftChild = 0;
    int RightChild = 0;

    std::cin >> Index >> LeftChild >> RightChild;

    Nodes[Index].LeftChild = LeftChild;
    if (LeftChild != -1)
    {
        Nodes[LeftChild].Parent = Index;
    }

    Nodes[Index].RightChild = RightChild;
    if (RightChild != -1)
    {
        Nodes[RightChild].Parent = Index;
    }
}

이는 입력받는 코드이다.
입력받은 대로, 왼쪽 자식과 오른쪽 자식을 저장해주었으며, 각 자식 노드의 부모를 현재 노드의 인덱스로 갱신해주었다.
 

for (int i = 1; i <= NumNode; i++)
{
    Nodes[i].Position = GetPosition(Nodes, i);
}

이후, GetPosition이라는 함수를 통해, 모든 노드의 position을 갱신해주었다.
GetPosition 함수 내부를 보자.
 

int GetPosition(std::vector<Node>& _Nodes, int _Index)
{
    int Parent = _Nodes[_Index].Parent;

    if(_Nodes[_Index].Position != 0)
    {
        return _Nodes[_Index].Position;
    }

    //내가 오른쪽 자식일 때.
    if (Parent != -1 && _Nodes[Parent].RightChild == _Index)
    {
        _Nodes[_Index].Position = GetPosition(_Nodes, Parent) + GetLeftSize(_Nodes, _Index) + 1;
        return _Nodes[_Index].Position;
    }

    //내가 왼쪽 자식일 때
    if (Parent != -1 && _Nodes[Parent].LeftChild == _Index)
    {
        _Nodes[_Index].Position = GetPosition(_Nodes, Parent) - GetRightSize(_Nodes, _Index) - 1;
        return _Nodes[_Index].Position;
    }

    //루트노드면?
    _Nodes[_Index].Position = GetLeftSize(_Nodes, _Index) + 1;
    return GetLeftSize(_Nodes, _Index) + 1;
}

위에서 설명했던 것을 동일하게 구현하였다.
 
GetLeftSize와 GetRightSize 함수 내부 코드는 뒤에서 보도록 하고, 의미만 먼저 알아보도록 하다.
GetLeftSize는 왼쪽 서브트리의 노드 개수이며, GetRightSize는 오른쪽 서브트리의 노드 개수이다.
 
현재, 내가 부모 노드의 오른쪽 자식이라고 한다면, 나의 위치는 부모 노드의 위치 + 왼쪽 서브트리의 개수  + 1이 된다.
반면 내가 부모 노드의 왼쪽 자식이라고 한다면, 나의 위치는 부모 노드의 위치 + 우측 서브트리의 개수  - 1이 된다.
 
이 공식을 그대로 적용하였다.
 
반면, 루트노드의 경우 부모노드가 없으므로 좌측 서브트리의 개수 + 1만 해주면 된다.

int GetLeftSize(std::vector<Node>& _Nodes, int _Index)
{
    if (_Nodes[_Index].LeftChild == -1)
    {
        return 0;
    }

    int LeftLeftSize = GetLeftSize(_Nodes, _Nodes[_Index].LeftChild);
    int LeftRightSize = GetRightSize(_Nodes, _Nodes[_Index].LeftChild);

    return LeftLeftSize + LeftRightSize + 1;
}

int GetRightSize(std::vector<Node>& _Nodes, int _Index)
{
    if (_Nodes[_Index].RightChild == -1)
    {
        return 0;
    }

    int LeftLeftSize = GetLeftSize(_Nodes, _Nodes[_Index].RightChild);
    int LeftRightSize = GetRightSize(_Nodes, _Nodes[_Index].RightChild);

    return LeftLeftSize + LeftRightSize + 1;
}

위 코드는 왼쪽 서브트리의 노드 개수를 구하는 함수와 오른쪽 서브트리의 노드 개수를 구하는 함수이다.
각 자식에 대해 재귀적으로 함수를 호출하여 노드 개수를 구하고 있다.
 
DFS방식과 동일하다고 보면 된다.
특정 노드의 서브트리의 노드 개수는 서브트리의 루트노드의 왼쪽 서브트리 노드 개수 + 오른쪽 서브트리 노드 개수 + 1 이기 때문에, 이를 이용하여 노드 개수를 구하였다. (1을 더하는 이유는 서브트리의 루트노드도 포함해야 하기 때문)
 

std::vector<std::pair<int, int>> MinMaxWidth(NumNode + 1, { INT_MAX, INT_MIN });

int RootNodeIndex = GetRootNode(Nodes, 1);
Nodes[RootNodeIndex].Level = 1;

std::queue<int> BFS;
BFS.push(RootNodeIndex);

모든 노드의 위치를 구하였다면, 이젠 너비를 구할 차례이다.
 
먼저, 너비를 구하기 위해 MinMaxWidth라는 자료구조를 만들었다.
해당 자료구조는 특정 레벨에서 가장 왼쪽에 있는 위치 값과 가장 오른쪽에 있는 위치 값을 저장할 벡터이다.
이 벡터의 인덱스는 레벨을 의미한다.
 
그리고, 레벨이 1인 루트 노드부터 시작해야 하기 때문에 루트노드를 구해서 루드노드의 level을 1로 초기화해주고 BFS를 시작하도록 하였다.
 

int GetRootNode(std::vector<Node>& _Nodes, int _Index)
{
    if (_Nodes[_Index].Parent == -1)
    {
        return _Index;
    }

    return GetRootNode(_Nodes, _Nodes[_Index].Parent);
}

참고로 루트노드를 구하는 함수는 위와 같다. 아무 노드나 하나 잡아서 부모를 타고 계속 올라가면 된다.
부모가 -1인 노드가 루트노드이므로 해당 인덱스를 반환하면 된다.
 

while (BFS.size() > 0)
{
    int CurIndex = BFS.front();
    BFS.pop();

    int Parent = Nodes[CurIndex].Parent;
    if (Parent != -1)
    {
        Nodes[CurIndex].Level = Nodes[Parent].Level + 1;
    }

    int CurLevel = Nodes[CurIndex].Level;

    MinMaxWidth[CurLevel].first = std::min(Nodes[CurIndex].Position, MinMaxWidth[CurLevel].first);
    MinMaxWidth[CurLevel].second = std::max(Nodes[CurIndex].Position, MinMaxWidth[CurLevel].second);

    if (Nodes[CurIndex].LeftChild != -1)
    {
        BFS.push(Nodes[CurIndex].LeftChild);
    }

    if (Nodes[CurIndex].RightChild != -1)
    {
        BFS.push(Nodes[CurIndex].RightChild);
    }
}

위 코드는 BFS의 구현 코드이다.
노드의 Level을 부모 노드의 Level + 1로 갱신해준 뒤, 노드의 위치값을 이용해 MinMaxWidth의 값을 갱신해주었다.
왼쪽 자식과 오른쪽 자식을 계속 queue에 삽입해주며 완전탐색을 돌려주었다.
 

//레벨, 길이
std::pair<int, int> Answer;

for (int i = 1; i <= NumNode; i++)
{
    int Width = MinMaxWidth[i].second - MinMaxWidth[i].first + 1;

    if (Width > Answer.second)
    {
        Answer.first = i;
        Answer.second = Width;
    }
}

MinMaxWidth가 모두 갱신되었으니, 이제 MinMaxWidth에 저장된 값을 이용해 Width의 최대값을 구할 차례이다.
MinMaxWidth의 값은 특정 레벨의 가장 왼쪽 위치값과 가장 오른쪽 위치값이므로 second - first + 1이 너비가 된다.
 
너비의 최대값을 구해주었다.
 

std::cout << Answer.first << " " << Answer.second;

return 0;

마지막으로 출력해주면 된다.
 

 

코드 전문

#include <iostream>
#include <vector>
#include <queue>
#include <climits>
#include <algorithm>

void Init()
{
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    std::cout.tie(nullptr);
}

struct Node
{
    int Level = 0;
    int Position = 0;
    
    int Parent = -1;
    int LeftChild = 0;
    int RightChild = 0;
};

//전방선언
int GetRightSize(std::vector<Node>& _Nodes, int _Index);

//구현부
int GetLeftSize(std::vector<Node>& _Nodes, int _Index)
{
    if (_Nodes[_Index].LeftChild == -1)
    {
        return 0;
    }

    int LeftLeftSize = GetLeftSize(_Nodes, _Nodes[_Index].LeftChild);
    int LeftRightSize = GetRightSize(_Nodes, _Nodes[_Index].LeftChild);

    return LeftLeftSize + LeftRightSize + 1;
}

int GetRightSize(std::vector<Node>& _Nodes, int _Index)
{
    if (_Nodes[_Index].RightChild == -1)
    {
        return 0;
    }

    int LeftLeftSize = GetLeftSize(_Nodes, _Nodes[_Index].RightChild);
    int LeftRightSize = GetRightSize(_Nodes, _Nodes[_Index].RightChild);

    return LeftLeftSize + LeftRightSize + 1;
}

int GetPosition(std::vector<Node>& _Nodes, int _Index)
{
    int Parent = _Nodes[_Index].Parent;

    if(_Nodes[_Index].Position != 0)
    {
        return _Nodes[_Index].Position;
    }

    //내가 오른쪽 자식일 때.
    if (Parent != -1 && _Nodes[Parent].RightChild == _Index)
    {
        _Nodes[_Index].Position = GetPosition(_Nodes, Parent) + GetLeftSize(_Nodes, _Index) + 1;
        return _Nodes[_Index].Position;
    }

    //내가 왼쪽 자식일 때
    if (Parent != -1 && _Nodes[Parent].LeftChild == _Index)
    {
        _Nodes[_Index].Position = GetPosition(_Nodes, Parent) - GetRightSize(_Nodes, _Index) - 1;
        return _Nodes[_Index].Position;
    }

    //루트노드면?
    _Nodes[_Index].Position = GetLeftSize(_Nodes, _Index) + 1;
    return GetLeftSize(_Nodes, _Index) + 1;
}

int GetRootNode(std::vector<Node>& _Nodes, int _Index)
{
    if (_Nodes[_Index].Parent == -1)
    {
        return _Index;
    }

    return GetRootNode(_Nodes, _Nodes[_Index].Parent);
}

int main()
{
    Init();

    int NumNode = 0;
    std::cin >> NumNode;

    std::vector<Node> Nodes(NumNode + 1);
    for (int i = 1; i <= NumNode; i++)
    {
        int Index = 0;
        int LeftChild = 0;
        int RightChild = 0;

        std::cin >> Index >> LeftChild >> RightChild;

        Nodes[Index].LeftChild = LeftChild;
        if (LeftChild != -1)
        {
            Nodes[LeftChild].Parent = Index;
        }

        Nodes[Index].RightChild = RightChild;
        if (RightChild != -1)
        {
            Nodes[RightChild].Parent = Index;
        }
    }

    for (int i = 1; i <= NumNode; i++)
    {
        Nodes[i].Position = GetPosition(Nodes, i);
    }
    
    //특정 레벨의 가장 왼쪽 위치값, 가장 오른쪽 위치값
    std::vector<std::pair<int, int>> MinMaxWidth(NumNode + 1, { INT_MAX, INT_MIN });
    
    int RootNodeIndex = GetRootNode(Nodes, 1);
    Nodes[RootNodeIndex].Level = 1;

    std::queue<int> BFS;
    BFS.push(RootNodeIndex);

    while (BFS.size() > 0)
    {
        int CurIndex = BFS.front();
        BFS.pop();

        int Parent = Nodes[CurIndex].Parent;
        if (Parent != -1)
        {
            Nodes[CurIndex].Level = Nodes[Parent].Level + 1;
        }

        int CurLevel = Nodes[CurIndex].Level;

        MinMaxWidth[CurLevel].first = std::min(Nodes[CurIndex].Position, MinMaxWidth[CurLevel].first);
        MinMaxWidth[CurLevel].second = std::max(Nodes[CurIndex].Position, MinMaxWidth[CurLevel].second);

        if (Nodes[CurIndex].LeftChild != -1)
        {
            BFS.push(Nodes[CurIndex].LeftChild);
        }

        if (Nodes[CurIndex].RightChild != -1)
        {
            BFS.push(Nodes[CurIndex].RightChild);
        }
    }

    //레벨, 길이
    std::pair<int, int> Answer;

    for (int i = 1; i <= NumNode; i++)
    {
        int Width = MinMaxWidth[i].second - MinMaxWidth[i].first + 1;

        if (Width > Answer.second)
        {
            Answer.first = i;
            Answer.second = Width;
        }
    }

    std::cout << Answer.first << " " << Answer.second;

    return 0;
}