문제 출처

1. 문제설명

  • 임의의 이진 트리가 입력으로 주어질 때 너비가 가장 넓은 레벨과 그 레벨의 너비를 구하라
  • 한 칸에는 하나의 노드만 존재할 수 있다.
  • 어떤 노드의 왼쪽 자식 노드는 해당 노드보다 왼쪽에 있고, 그 반대 또한 해당 노드보다 오른쪽에 있어야 한다.

  • 노드가 배치된 가장 왼쪽과 오른쪽 사이엔 아무 노드도 없이 비어있는 열은 없다.

  • 문제 분류
    • Graph, Tree, DFS


2. 알고리즘 설계

  • 어떤 트리인지에 대한 이해는 이미지를 보면 이해 가능할 것이다.
  • 문제를 읽어보면 inorder(left child-root-right child)로 탐색한다.
    • inorder의 형태는 다음과 같다.
    void inorder(int cur) {
  inorder(cur->left);
  print(cur);
  inorder(cur->right);
}
    • 여기서 print(cur)를 대신해, 좌/우 인덱스의 위치를 구할 것이다.
  • 재귀적인 특성으로 인해 트리의 각 레벨을 탐색하면서 위치 정보를 갱신할 수 있다.
    • 이미지를 보면 한 칸에는 하나의 노드만 삽입될 수 있어, idx 변수를 통해 따로 관리해야 한다.
  • 이후에는 각 트리의 레벨에서 좌/우 값을 서로 빼준 값에 1을 더해 최댓값을 구해주면 된다.
  • 맞왜틀을 시전할 수 있는 포인트
    • 시작 노드는 무조건 1은 아니다.
    • 2로 시작할 수도 3으로 시작할 수도 있다.
    • inorder(root, 1); 이 부분을 반드시 루트로 설정해야 코드가 잘 작동한다.


3. 전체 코드

#include <bits/stdc++.h>
using namespace std;
using pii = pair<int,int>;

const int SZ=10'002, INF=987654321;
int n, p, l, r, root, idx=1;
pii tree[SZ];
int low[SZ], high[SZ], is_root[SZ];

void inorder(int cur, int d) {
    if(cur < 1) return;

    inorder(tree[cur].first, d+1);
    low[d] = min(low[d], idx);
    high[d] = max(high[d], idx++);
    inorder(tree[cur].second, d+1);
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);

    cin >> n;
    fill(low, low+n+1, INF);

    for(int i=1; i<=n; i++) {
        cin >> p >> l >> r;
        tree[p] = {l, r};

        is_root[p]++;
        if(l != 1) is_root[l]++;
        if(r != 1) is_root[r]++;
    }

    for(int i=1; i<=n; i++)
        if(is_root[i] == 1)
            root = i;

    inorder(root, 1);
    
    int lv = 1, width = high[1] - low[1] + 1;
    for(int i=2; i<=n; i++) {
        int cmp = high[i] - low[i] + 1;
        if(cmp > width) {
            width = cmp;
            lv = i;
        }
    }

    cout << lv << ' ' << width;

    return 0;
}