[c++] BOJ 2250 :: 트리의 높이와 너비

난이도 : 골드 2

걸린 시간 : 1시간

 

문제

트리의 높이와 너비 문제 바로가기

이진트리를 다음의 규칙에 따라 행과 열에 번호가 붙어있는 격자 모양의 틀 속에 그리려고 한다. 이때 다음의 규칙에 따라 그리려고 한다.

1. 이진트리에서 같은 레벨(level)에 있는 노드는 같은 행에 위치한다.
2. 한 열에는 한 노드만 존재한다.
3. 임의의 노드의 왼쪽 부트리(left subtree)에 있는 노드들은 해당 노드보다 왼쪽의 열에 위치하고, 오른쪽 부트리(right subtree)에 있는 노드들은 해당 노드보다 오른쪽의 열에 위치한다.
4. 노드가 배치된 가장 왼쪽 열과 오른쪽 열 사이엔 아무 노드도 없이 비어있는 열은 없다.

이와 같은 규칙에 따라 이진트리를 그릴 때 각 레벨의 너비는 그 레벨에 할당된 노드 중 가장 오른쪽에 위치한 노드의 열 번호에서 가장 왼쪽에 위치한 노드의 열 번호를 뺀 값 더하기 1로 정의한다. 트리의 레벨은 가장 위쪽에 있는 루트 노드가 1이고 아래로 1씩 증가한다.

우리는 주어진 이진트리를 위의 규칙에 따라 그릴 때에 너비가 가장 넓은 레벨과 그 레벨의 너비를 계산하려고 한다. 위의 그림의 예에서 너비가 가장 넓은 레벨은 3번째와 4번째로 그 너비는 18이다. 너비가 가장 넓은 레벨이 두 개 이상 있을 때는 번호가 작은 레벨을 답으로 한다. 그러므로 이 예에 대한 답은 레벨은 3이고, 너비는 18이다.

임의의 이진트리가 입력으로 주어질 때 너비가 가장 넓은 레벨과 그 레벨의 너비를 출력하는 프로그램을 작성하시오

 

풀이

• 각 노드의 열을 구하려면 트리를 중위순회하면 된다.

 

코드

#include <iostream>
#include <vector>

using namespace std;

struct Node {
    int data;
    Node* leftChild = nullptr;
    Node* rightChild = nullptr;
    Node* rootNode = nullptr;
    Node(int d) {
        int data = d;
    }
};

Node* nodeArr[10001];
int nowPos = 1; // 현재 열
int level = 0; // 현재 레벨
int maxLevel = 0; // 최대 레벨 저장
int root = 0; // 루트 노드 idx 저장
vector<vector<int>> width(10001, vector<int>()); // 각 레벨의 열 저장

void Inorder(Node* nodePtr) {
    if (level > maxLevel)
        maxLevel = level;

    if (nodePtr->leftChild != nullptr) {
        level++;
        Inorder(nodePtr->leftChild);
        level--;
    }
    width[level].push_back(nowPos++);
    if (nodePtr->rightChild != nullptr) {
        level++;
        Inorder(nodePtr->rightChild);
        level--;
    }
}

Node* findRoot(Node* nodePtr) { // rootNode를 저장하여 위로 타고 올라가기
    while (nodePtr->rootNode != nullptr) {
        nodePtr = nodePtr->rootNode;
    }
    return nodePtr;
}

int main() {
    // 50분
    // 중위 순회!, 연결리스트

    int N; cin >> N;

    Node* head;
    for (int i = 1; i <= N; i++) { // 노드 삽입
        Node* newNode = new Node(i);
        newNode->data = i;
        nodeArr[i] = newNode;
    }


    for (int i = 1; i <= N; i++) { // 연결 리스트 만들기
        int n, l, r; cin >> n >> l >> r;
        Node* node = nodeArr[n];
        if (l != -1) {
            node->leftChild = nodeArr[l];
            nodeArr[l]->rootNode = node;
        }
        if (r != -1) {
            node->rightChild = nodeArr[r];
            nodeArr[r]->rootNode = node;
        }
    }

    Node* rootNode = findRoot(nodeArr[1]); // root는 첫번째로 주어진 노드가 아닐 수도 있음
    Inorder(rootNode);

    int maxResult = 0; int resultLv = 0;
    for (int i = 1; i <= maxLevel; i++) {
        int tmpWidth = width[i][width[i].size() - 1] - width[i][0];
        if (tmpWidth > maxResult) {
            maxResult = tmpWidth;
            resultLv = i;
        }
    }
    cout << resultLv+1 << " " << maxResult+1;
}

 

주의할 점

• 항상 초기화, 처음 값이 잘 들어가 있어야 한다.
• 여기에서는 노드가 각 레벨에 하나밖에 없을 때 width가 1이 됨을 만족 해야한다.
• 첫번째로 주어진 노드가 root node가 아닐 수 있다.

 

 

결과

아이디	메모리	시간	언어	코드 길이
gmldms784	2868	12	C++17 / 수정	1661