트리의 높이와 너비 (boj 2250)

트리의 높이와 너비 문제는 각 노드마다 자식 노드의 번호를 2개 주고, 이를 이진트리로 만든 뒤 DFS하는 문제에요 (Postorder search)

 

아래 코드를 보시면

children 배열에 자식노드를, parent 노드에 부모 노드를 저장하여 이진트리를 구성했어요.

그리고 빈 column 없이 트리를 구성해야한다는 점을 이용하면, 왼쪽 자식 서브 트리가 차지한 최대 column + 1 이 자기 자신의 노드 column index가 된다는 것을 알 수 있죠. 이후 오른쪽 자식노드의 maxIndex를 구하는 이유는 내 부모 노드의 위치를 결정해주어야 하기 때문이에요.

DFS를 통해 재귀적으로 자식의 maxIndex 부터 알아가며 자기 자신의 위치를 결정하고, 그렇게 결정된 위치를 통해 레벨 별 최소 최대 인덱스를 적절히 계산하여 너비를 구해내면 답을 쉽게 찾을 수 있습니다.

 

코드

#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <algorithm>
#include <vector>

#define INF 987654321

int N;

// 자식 노드 (first = 왼쪽 노드, second = 오른쪽 자식 노드)
std::pair<int, int> children[10010];

// 부모 노드
int parent[10010];

// 최종 결과 (first = 해당 레벨에서 가장 작은 column index, second = 해당 레벨에서 가장 큰 column index)
std::pair<int, int> result[10010];

// 트리 루트
int root;

/**
 * 트리 순회 함수
 * @param curNode 현재 방문하고 있는 노드
 * @param level  현재 방문하고 있는 노드의 레벨
 * @param startColumn 현재 노드가 가질 수 있는 최소 column index - 1     즉, 현재까지 노드로 차 있는 column index 라고 생각하면 좋음
 * @return 현재 노드가 구성하는 서브트리의 max column index
 */
int DFS(int curNode, int level, int startColumn) {
    // 유효하지 않은 노드번호인 경우 startColumn 자체가 max column index
    if (curNode == 0)
        return startColumn;

    // 왼쪽 자식의 max column index 를 구함
    int left = DFS(children[curNode].first, level + 1, startColumn);

    // 나 자신은 왼쪽 자식의 max column index 바로 다음 것에 저장됨
    int position = left + 1;

    // 현재 level에서 나 자신이 가장 최소 index 이거나 최대 index 일 수 있으니 이를 업데이트
    result[level].first = std::min(result[level].first, position);
    result[level].second = std::max(result[level].second, position);

    // 오른쪽 자식의 maxIndex
    int right = DFS(children[curNode].second, level + 1, position);
    return right;
}

int main() {
    scanf("%d", &N);

    for (int n = 1; n <= N; n++) {
        int num, left, right;
        scanf("%d %d %d", &num, &left, &right);
        if (left == -1)
            left = 0;

        if (right == -1)
            right = 0;

        // 트리 구성
        // 노드 num 의 왼쪽 오른쪽 자식 노드를 세팅
        children[num].first = left;
        children[num].second = right;

        // 왼쪽 오른쪽 자식 노드 입장에서는 num이 부모 노드
        parent[left] = num;
        parent[right] = num;

        result[n].first = INF;
    }

    for (int n = 1; n <= N; n++) {
        // 부모가 없는 노드가 루트노드
        if (!parent[n]) {
            root = n;
            break;
        }
    }

    // DFS 돌리면 level 별로 최소 인덱스와 최대 인덱스가 저장되어 나옴
    DFS(root, 1, 0);

    int n1 = 0, n2 = 0;
    for (int n = 1; n <= N; n++) {
        // 최대 너비 찾기
        int width = result[n].second - result[n].first + 1;
        if (n1 < width) {
            n1 = width;
            n2 = n;
        }
    }
    printf("%d %d\n", n2, n1);
    return 0;
}