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

문제 출처 :

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

알고리즘 분석 :

문제 해결에 필요한 사항

1. Tree에 대한 이해

2. dfs

3. 중위 순회

중위 순회에 대한 간단한 내용 :: http://www.crocus.co.kr/348

이 문제는 처음 접하게 되면 어떻게 시작해야 할 지 막막할 수 도 있다.

하지만 자세히 보면 중위 순회를 통해 가장 왼쪽 값 부터 

위치를 찾아 나갈 수 있는 방식으로 구성되어 있다는 것을 확인 할 수 있다. 

중위 순회의 순서는

8->4->2->14->9->18->15->5->10->1->...->7로 끝이난다.

이 방식을 이용하여 문제를 해결한다.

문제 해결을 위해 

1. 트리를 생성해주고(자식 노드 연결)

2. 그 트리의 루트 노드를 찾는다.(1이 루트 노드가 아닐 때도 있다.)

3. 중위 순회(dfs)를 통해 각 레벨 및 위치를 저장한다.

4. 중위 순회 동안 각 레벨당 가장 왼쪽 노드, 가장 오른쪽 노드의 위치를 찾아낸다.

5. for문을 통해 최고 너비를 가진 레벨을 찾아낸다.

소스 코드 : 

#include <iostream>
#include <cstdio>
#include <limits.h>
 
using namespace std;
 
typedef pair<int, int> pii;
 
pii tree[10002]; // first = left, second = right
pii len[10002]; // first = level , second = len
int minarr[10002];
int maxarr[10002];
 
long long int sum, maxval, level;
 
int real[10002];
int target;
 
int pos = 1; // 노드의 위치
 
// 전위 순회 dfs
void dfs(int now, int level)
{
    // 왼쪽 자식이 있다면
    if (tree[now].first > 0)
        dfs(tree[now].first, level + 1);
 
    // 현재 레벨 및 위치 저장
    len[now].first = level;
    len[now].second = pos;
 
    // 현재 레벨에서 가장 왼쪽 노드 위치를 갱신
    if (minarr[len[now].first] > len[now].second)
        minarr[len[now].first] = len[now].second;
 
    // 현재 레벨에서 가장 오른쪽 노드 위치를 갱신
    if (maxarr[len[now].first] < len[now].second)
        maxarr[len[now].first] = len[now].second;
 
    pos++;
 
    // 오른쪽 자식이 있다면
    if (tree[now].second > 0)
        dfs(tree[now].second, level + 1);
}
 
int main()
{
    int n;
    int root, left, right;
    scanf("%d", &n);
 
    // min값을 찾기 위해 INT_MAX로 전체를 초기화
    fill(minarr, minarr + 10002, INT_MAX);
 
    // 트리 생성
    for (int i = 1; i <= n; i++)
    {
        scanf("%d %d %d", &root, &left, &right);
        tree[root].first = left;
        tree[root].second = right;
    
        real[root]++;
 
        if (left != -1)
            real[left]++;
        if (right != -1)
            real[right]++;
    }
 
    // 루트 노드 찾기
    for (int i = 1; i <= n; i++)
        if (real[i] == 1)
            target = i;
 
    dfs(target, 1);
    
    // 각 레벨의 최대 - 최소 + 1을 하여 
    // 트리의 최대 너비 및 레벨을 구하는 과정
    for (int i = 1; i <= n; i++)
    {
        sum = maxarr[i] - minarr[i] + 1;
        if (sum > maxval)
        {
            maxval = sum;
            level = i;
        }
    }
 
    printf("%lld %lld", level, maxval);
    return 0;
}
 
//                                                       This source code Copyright belongs to Crocus
//                                                        If you want to see more? click here >>