[백준] 2250번: 트리의 높이와 너비 - inorder 탐색, 루트 노드 찾기

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

예제 

19
1 2 3
2 4 5
3 6 7
4 8 -1
5 9 10
6 11 12
7 13 -1
8 -1 -1
9 14 15
10 -1 -1
11 16 -1
12 -1 -1
13 17 -1
14 -1 -1
15 18 -1
16 -1 -1
17 -1 19
18 -1 -1
19 -1 -1

ans :
3 18

---

depth와 col을 구하면 된다. depth는 dfs와 함께 부모의 depth + 1로 구할 수 있다. col이 문제가 되는데 col을 구하는 방법은 처음에 두 가지를 떠올렸다.

1. 각 레벨의 가장 왼쪽 노드와 가장 오른쪽 노드 사이의 노드 개수 구하기 -> width
2. dp로 푸는데, dp [k] = k 레벨의 width로 두고 dp [k+1] = dp [k] + k 레벨의 가장 왼쪽 노드부터 k+1 레벨의 가장 왼쪽 노드 사이에 있는 노드의 수 + 오른쪽도 같은 방법으로 구하기

두 방법 모두 특정 노드를 기준으로 왼쪽엔 어떤 노드가 있고 오른쪽엔 어떤 노드가 있는지 구해야 한다. dfs를 할 때 구할 수 있을 것 같은데 매우 복잡하고 시간 복잡도 계산도 힘들었다. 따라서 이 풀이는 아니라고 판단하고 다시 문제에서 제시한 규칙에 집중했다.

 

보통 문제에서 규칙을 자세하게 명시하는 경우 규칙을 그대로 구현하거나 규칙에서 패턴을 찾아내서 구현하는 풀이가 많았기에 이번에도 규칙을 뜯어보았다. 

그러다가 규칙을 찾았는데 열을 채우는 방식이 inorder의 방문 순서와 똑같다는 점이었다. 가장 왼쪽을 1로 하고, 또 다음 서브트리에서 가장 왼쪽부터 방문하고 이 방식이 inorder와 똑같아서 inorder를 구현하면 끝이다!

 

또 주의해야 하는게 root가 1이 아니고 부모가 없는 노드가 루트 노드라는 점이었다. 부모가 없는 노드를 루트로 정하는 로직도 기억해 두면 쓸 곳이 많아 보인다.

/** Tree 2250 트리의 높이와 너비 **/
#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
using namespace std;
int n, root = 1, col_idx = 1, depth_max_idx = 0;
// adj[i][0] : left child, adj[i][1] : right child
vector<int> adj[10002];
vector<int> depth[10002];
int node_col[10002];

void inorder(int cur, int d)
{
    if (cur == -1)
        return;
    inorder(adj[cur][0], d + 1);

    node_col[cur] = col_idx++;

    depth[d].push_back(cur);
    depth_max_idx = max(depth_max_idx, d);

    inorder(adj[cur][1], d + 1);
}

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    cin >> n;

    vector<bool> isRoot(n + 1, true);

    for (int i = 1; i <= n; i++)
    {
        int cur, l, r;
        cin >> cur >> l >> r;
        adj[cur].push_back(l);
        adj[cur].push_back(r);

        if (l != -1)
            isRoot[l] = false;
        if (r != -1)
            isRoot[r] = false;
    }

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

    inorder(root, 1);

    int ans = 0, level = 0;
    for (int i = 1; i <= depth_max_idx; i++)
    {
        int min_col = n, max_col = 0;
        for (auto x : depth[i])
        {
            min_col = min(min_col, node_col[x]);
            max_col = max(max_col, node_col[x]);
        }
        if (ans < max_col - min_col + 1)
        {
            ans = max_col - min_col + 1;
            level = i;
        }
    }
    cout << level << ' ' << ans;
}