BOJ2250: 트리의 높이와 너비

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

  • 책정된 난이도에 비해 문제가 너무 쉽지 않았나 싶다.
  • inoder와 depth를 찾은 뒤 잘 정리만 해주면 끝.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
#include <bits/stdc++.h>
using namespace std;

class Tree {
  int N, in = 0, root;
  vector<int> left, right, indegree;
  map<int, int> depth2min, depth2max;
public:
  Tree(int n): N(n), left(n+1), right(n+1), indegree(n+1) {}
  void input();
  void dfs(int u = -1, int depth = 1);
  void solve();
};

void Tree::input() {
  for(int i = 0; i < N; i++) {
    int p, l, r;
    cin >> p >> l >> r;
    left[p] = l, right[p] = r;
    if(r != -1) indegree[r]++;
    if(l != -1) indegree[l]++;
  }
  for(int i = 1; i <= N; i++)
    if(indegree[i] == 0)
      root = i;
}

void Tree::dfs(int u, int depth) {
  if (u == -1) u = root;
  if(left[u] != -1) dfs(left[u], depth+1);

  if(!depth2min.count(depth))
    depth2min[depth] = 99999, depth2max[depth] = 0;
  depth2min[depth] = min(depth2min[depth], ++in);
  depth2max[depth] = max(depth2max[depth], in);

  if(right[u] != -1) dfs(right[u], depth+1);
}

void Tree::solve() {
  int maxW = 0, maxD = 0;
  for(auto [depth, minPost] : depth2min) {
    int widht = depth2max[depth] - minPost + 1;
    if(maxW < widht)
      maxW = widht, maxD = depth;
  }
  printf("%d %d", maxD, maxW);
}

int main() {
  int N;
  cin >> N;
  Tree tree(N);
  tree.input();
  tree.dfs();
  tree.solve();
}