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

문제 링크입니다: https://www.acmicpc.net/problem/2250

중위 순회(Inorder Traversal) DFS(Depth First Search) 알고리즘을 적용하여 푸는 문제였습니다.

알고리즘은 아래와 같습니다.

1. 트리를 입력 받을 때 pair<int, int>형 배열에 인덱스를 부모로 하고 자식들을 입력받습니다. 부모가 항상 1이 아니기 때문에 입력받는 노드를 세서 한번만 입력되는 노드를 루트로 정합니다.

2. 중위 순회 DFS를 실행합니다. 이 때, 해당 높이에서 제일 좌측에 있는 노드와 제일 우측에 있는 노드를 업데이트합니다.

3. 각 레벨을 탐색하면서 제일 긴 길이를 구하고 해당 높이와 길이를 출력합니다.

주의할 점은, 1번에서도 언급했듯이 1번 노드가 항상 루트가 아니라는 점입니다!

#include <iostream>

#include <algorithm>

using namespace std;

 

const int MAX = 10000 + 1;

const int INF = 987654321;

 

int N, nodeIdx; //N과 노드의 위치

int node[MAX]; //루트 찾기 위해

int low[MAX];

int high[MAX];

pair<int, int> tree[MAX];

 

//Inorder Traversal(중위 순회)

void DFS(int nodeNum, int cnt)

{

        //left SubTree

        if (tree[nodeNum].first > 0)

                 DFS(tree[nodeNum].first, cnt + 1);

 

        //Visit

        low[cnt] = min(low[cnt], nodeIdx);

        high[cnt] = max(high[cnt], nodeIdx++);

 

        //right SubTree

        if (tree[nodeNum].second > 0)

                 DFS(tree[nodeNum].second, cnt + 1);

}

 

int main(void)

{

        ios_base::sync_with_stdio(0);

        cin.tie(0); //cin 속도 향상

        cin >> N;

 

        for (int i = 0; i < MAX; i++)

                 low[i] = INF;

 

        for (int i = 0; i < N; i++)

        {

                 int parent, child1, child2;

                 cin >> parent >> child1 >> child2;

 

                 node[parent]++;

                

                 if (child1 != -1)

                         node[child1]++;

                 tree[parent].first = child1;

                 if (child2 != -1)

                         node[child2]++;

                 tree[parent].second = child2;

        }

 

        //루트 찾기

        int root;

        for (int i = 1; i <= N; i++)

                 if (node[i] == 1)

                         root = i;

 

        //DFS

        nodeIdx = 1;

        DFS(root, 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";

        return 0;

}

개발환경:Visual Studio 2017

지적, 조언, 질문 환영입니다! 댓글 남겨주세요~