트리의 높이와 너비

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

답을 보지 않고 풀어냈는데, 풀고나서 답을 찾아보니 내가 푼 방법보다 훨씬 깔끔한 방법이 있었다.

물론, 두 가지 방법 모두 시간 복잡도 측면에서 큰 차이는 없다.

훨씬 깔끔한 방법이 내 풀이를 어느정도 포괄하는 측면이 있기에 훨씬 깔끔한 방법을 기준으로 설명하고, 내 풀이는 기록 보존을 위해 후술한다.

• 각 노드가 어떤 컬럼에 적히게 될 것인가는 잘 생각해보면 그냥 중위 순회 순서와 같음을 알 수 있다.
• 따라서, 중위 순회를 통해서 각 노드가 적힐 컬럼을 구해준다.
• 각 노드의 레벨을 재귀 또는 BFS를 통해 구한 뒤에 레벨 별로 너비를 구해본다.

내가 캐치하지 못했던 점은 각 노드의 중위 순회에서의 방문 순서가 곧 적히는 컬럼이라는 점이었다.

나는 각 노드가 적히는 위치는 그 노드의 왼쪽 서브트리 크기 만큼이 쓰인 직후가 된다는 사실에 집중했다.

매번 재귀를 진행할 때마다 offset(후보 컬럼이 될 수 있는 가장 빠른 곳)을 전달하고 왼쪽 서브트리 크기를 사용하여 문제를 풀어주었다.

별로 좋은 방법은 아닌 듯 하다.

#include <iostream>

using namespace std;

const int kMaxN = 10000;

struct Node
{
  int size_;
  int level_;
  int position_;
  Node* left_;
  Node* right_;
};

int N;
Node NODES[kMaxN + 1];
int LEFTMOSTS[kMaxN + 1];
int RIGHTMOSTS[kMaxN + 1];
int IS_NOT_ROOT[kMaxN + 1];

int UpdateSizeAndLevel(Node* root, const int level)
{
  if (!root)
  {
    return 0;
  }

  root->level_ = level;

  root->size_ = 1;
  root->size_ += UpdateSizeAndLevel(root->left_, level + 1);
  root->size_ += UpdateSizeAndLevel(root->right_, level + 1);

  return root->size_;
}

void UpdatePosition(Node* root, const int offset)
{
  if (!root)
  {
    return;
  }

  int left_size = (root->left_ == NULL) ? 0 : root->left_->size_;

  root->position_ = offset + left_size + 1;
  UpdatePosition(root->left_, offset);
  UpdatePosition(root->right_, root->position_);
}
void Solve(const int root)
{
  // Initialize
  for (int lv = 1; lv <= N; ++lv)
  {
    LEFTMOSTS[lv] = kMaxN * kMaxN;
    RIGHTMOSTS[lv] = 0;
  }

  // Solve
  UpdateSizeAndLevel(&NODES[root], 1);
  UpdatePosition(&NODES[root], 0);

  int max_level = -1;
  for (int i = 1; i <= N; ++i)
  {
    LEFTMOSTS[NODES[i].level_] = min(LEFTMOSTS[NODES[i].level_], NODES[i].position_);
    RIGHTMOSTS[NODES[i].level_] = max(RIGHTMOSTS[NODES[i].level_], NODES[i].position_);
    max_level = max(max_level, NODES[i].level_);
  }

  int ans_level = -1;
  int ans_width = -1;

  for (int lv = 1; lv <= max_level; ++lv)
  {
    int width = RIGHTMOSTS[lv] - LEFTMOSTS[lv] + 1;
    if (width > ans_width)
    {
      ans_level = lv;
      ans_width = width;
    }
  }

  cout << ans_level << ' ' << ans_width << '\n';
}

int main(void)
{
  // For Faster IO
  ios_base::sync_with_stdio(false);
  cout.tie(nullptr);
  cin.tie(nullptr);

  // Read Inputs
  cin >> N;
  for (int it = 0; it < N; ++it)
  {
    int parents, left, right;
    cin >> parents >> left >> right;

    NODES[parents].left_ = (left == -1) ? nullptr : &NODES[left];
    NODES[parents].right_ = (right == -1) ? nullptr : &NODES[right];

    if (left != -1)
    {
      IS_NOT_ROOT[left] = 1;
    }
    if (right != -1)
    {
      IS_NOT_ROOT[right] = 1;
    }
  }

  int root;
  for (int i = 1; i <= N; ++i)
  {
    if (IS_NOT_ROOT[i] == 0)
    {
      root = i;
      break;
    }
  }

  // Solve
  Solve(root);

  return 0;
}