[백준 2250] 트리의 높이와 너비 (C#, C++) - soo:bak

문제 링크

2250번 - 트리의 높이와 너비

설명

이진 트리를 특정 규칙에 따라 격자에 배치했을 때, 너비가 가장 넓은 레벨과 그 너비를 구하는 문제입니다.

접근법

트리를 중위순회하면 왼쪽 자식, 현재 노드, 오른쪽 자식 순서로 방문하게 됩니다. 이 방문 순서대로 열 번호를 1부터 차례로 부여하면 문제에서 요구하는 배치 규칙을 자연스럽게 만족합니다.

먼저 입력에서 각 노드의 자식 정보를 저장하고, 부모가 없는 노드를 찾아 루트로 삼습니다. 중위순회를 수행하면서 각 깊이별로 가장 작은 열 번호와 가장 큰 열 번호를 기록합니다.

모든 깊이에 대해 가장 큰 열에서 가장 작은 열을 뺀 값에 1을 더하면 그 레벨의 너비가 됩니다. 이 중 가장 큰 너비를 가진 레벨을 찾고, 너비가 같으면 레벨 번호가 작은 쪽을 선택합니다.

---

Code

C#

using System;

class Program {
  const int MAX = 10001;
  static int n, col = 1;
  static int[] left = new int[MAX], right = new int[MAX], parent = new int[MAX];
  static int[] levelMin = new int[MAX], levelMax = new int[MAX];

  static void Dfs(int node, int depth) {
    if (node == -1) return;
    Dfs(left[node], depth + 1);
    if (levelMin[depth] == 0 || levelMin[depth] > col) levelMin[depth] = col;
    if (levelMax[depth] < col) levelMax[depth] = col;
    col++;
    Dfs(right[node], depth + 1);
  }

  static void Main() {
    n = int.Parse(Console.ReadLine()!);
    for (var i = 0; i < n; i++) {
      var parts = Console.ReadLine()!.Split();
      var p = int.Parse(parts[0]);
      var l = int.Parse(parts[1]);
      var r = int.Parse(parts[2]);
      left[p] = l;
      right[p] = r;
      if (l != -1) parent[l] = p;
      if (r != -1) parent[r] = p;
    }

    var root = 1;
    for (var i = 1; i <= n; i++) if (parent[i] == 0) { root = i; break; }

    Dfs(root, 1);

    var bestLevel = 1;
    var bestWidth = levelMax[1] - levelMin[1] + 1;
    for (var d = 2; d <= n; d++) {
      if (levelMin[d] == 0) break;
      var width = levelMax[d] - levelMin[d] + 1;
      if (width > bestWidth) {
        bestWidth = width;
        bestLevel = d;
      }
    }

    Console.WriteLine($"{bestLevel} {bestWidth}");
  }
}

C++

#include <bits/stdc++.h>
using namespace std;

const int MAX = 10001;

int L[MAX], R[MAX], parentArr[MAX];
int levelMin[MAX], levelMax[MAX];
int colNum = 1;

void dfs(int node, int depth) {
  if (node == -1) return;
  dfs(L[node], depth + 1);
  if (levelMin[depth] == 0 || levelMin[depth] > colNum) levelMin[depth] = colNum;
  if (levelMax[depth] < colNum) levelMax[depth] = colNum;
  ++colNum;
  dfs(R[node], depth + 1);
}

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

  int n; cin >> n;
  for (int i = 0; i < n; i++) {
    int p, l, r; cin >> p >> l >> r;
    L[p] = l;
    R[p] = r;
    if (l != -1) parentArr[l] = p;
    if (r != -1) parentArr[r] = p;
  }

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

  dfs(root, 1);

  int bestLevel = 1, bestWidth = levelMax[1] - levelMin[1] + 1;
  for (int d = 2; d <= n; d++) {
    if (levelMin[d] == 0) break;
    int width = levelMax[d] - levelMin[d] + 1;
    if (width > bestWidth) {
      bestWidth = width;
      bestLevel = d;
    }
  }

  cout << bestLevel << " " << bestWidth << "\n";

  return 0;
}