백준 2250 트리의 높이와 너비(dfs, inorder traversal)

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

2250번: 트리의 높이와 너비

#include <iostream>
#include <vector>

using namespace std;
const int MAX = 10000 + 1;
int N;
vector<pair<int, int>> tree[MAX];
int nodeIndex;
int low[MAX];
int high[MAX];
int node[MAX];
int start;
void dfs(int root, int level)
{
    if (tree[root][0].first > 0)
    {
        dfs(tree[root][0].first, level + 1);
    }
    low[level] = min(low[level], nodeIndex);
    high[level] = max(high[level], nodeIndex++);

    if (tree[root][0].second > 0)
    {
        dfs(tree[root][0].second, level + 1);
    }
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    for (int i = 0; i <= MAX; i++)
    {
        low[i] = 987654321;
    }

    cin >> N;
    for (int i = 0; i < N; i++)
    {
        int parent, leftChild, rightChild;
        cin >> parent >> leftChild >> rightChild;
        node[parent]++;
        if (leftChild != -1)
            node[leftChild]++;
        if (rightChild != -1)
            node[rightChild]++;
        tree[parent].push_back(make_pair(leftChild, rightChild));
    }
    for (int i = 1; i <= N; i++)
    {
        if (node[i] == 1)
            start = i;
    }
    nodeIndex = 1;
    dfs(start, 1);
    int result = high[1] - low[1] + 1;

    int level = 1;

    for (int i = 2; i <= N; i++)
    {
        int temp = high[i] - low[i] + 1;
        if (temp > result)
        {
            result = temp;
            level = i;
        }
    }
    cout << level << " " << result << "\n";
}

또 jaimemin님 코드 봤다. 사실상 dfs문제라기 보다는 inorder traversal 문제라고 보는게 맞는것 같다.

 

inorder traversal을 하게 되면 이런 순서로 tree를 순회하게 된다. 순회하는 번호들을 유심히보면 알 수 있듯이 순회하는 순서가 결국 열의 번호와 일치하게 된다. 이를 이용해서 푸는 문제였다....

 

inorder traversal을 알고는 있었지만 이렇게 활용될 수 있을 거라고는 생각 못했다.

 

그리고 또 하나 발견한 사실은 int low[MAX]={987654321,} 와 같이 선언하면 배열 전체가 987654321로 초기화 된다고 착각하고 있었다....

 

https://www.uwangg.com/36

C++ 배열 초기화 방법

이 블로그에 굉장히 잘 설명이되어 있는데 0으로 전체 배열을 초기화 할 때만 저런식의 방법이 통하는 거지 다른 수로 초기화하고 싶을 때 저런 방법을 써서는 안된다.