[백준] 2250 트리의 높이와 너비

나와 있는 규칙을 통해서 가장 넓은 너비를 가지고 있는 행과 너비를 구해라

풀이방법

중위 순회를 통해서 우리는 열의 번호를 알 수 있다. 그리고 dfs로 노드를 들어가면서 행의 번호 또한 알 수 있다. 이를 통해서 행 당 너비를 알아내면 된다.

#include <cmath>
#include <iostream>

#define MAX 10000 + 1
#define INF ~(1 << 31)
using namespace std;
int is_node_parent[MAX], low[MAX], high[MAX], N, node_idx;
pair<int, int> node[MAX];

void DFS(int parent, int cnt) {

  if (node[parent].first > 0) {
    DFS(node[parent].first, cnt + 1);
  }

  low[cnt] = min(low[cnt], node_idx);
  high[cnt] = max(high[cnt], node_idx++);

  if (node[parent].second > 0) {
    DFS(node[parent].second, cnt + 1);
  }
}

int main() {
  int root;
  cin >> N;
  for (int i = 0; i < N + 1; i++) {
    low[i] = INF;
  }
  for (int i = 0; i < N; i++) {
    int parent, left, right;
    cin >> parent >> left >> right;
    is_node_parent[parent]++;
    if (left != -1)
      is_node_parent[left]++;
    if (right != -1)
      is_node_parent[right]++;
    node[parent] = make_pair(left, right);
  }

  for (int i = 0; i <= N; i++) {
    if (is_node_parent[i] == 1) {
      root = i;
    }
  }
  node_idx = 1;
  DFS(root, 1);

  int result = high[1] - low[1] + 1, level = 1;

  for (int i = 2; i < N + 1; i++) {
    int tmp = high[i] - low[i] + 1;
    if (result < tmp) {
      result = tmp;
      level = i;
    }
  }

  cout << level << ' ' << result << endl;
  return 0;
}

[백준] 2250 트리의 높이와 너비

Abstract

[백준] 2250번 트리의 높이와 너비

알고리즘 유형

문제 이해

풀이방법