[백준 2250] 트리의 높이와 너비

문제 링크 => 2250번: 트리의 높이와 너비 (acmicpc.net)

2250번: 트리의 높이와 너비

 

트리에 대한 문제이다.

 

문제 input 이 하나밖에 없어서 강박관념에 벗어나지 못할 만한 그런 문제이다. (간단하지만 어려운 문제)

먼저 문제 접근 방법은 다음과 같다.

 

1. 트리를 형성한다.

2. root 노드를 찾는다.

3. 중위 운행을 통해 해당 노드의 level, position을 부여한다.

4. level 별로 position 을 오름차순으로 정렬 후, 너비를 구한다.

5. 그 중에 너비가 가장 크면서 level이 가장 작은 게 답이다.

 

1, 3, 4, 5 는 사실 쉽게 접근이 가능하다.

그러나 2 번 case에서 단순히 문제에 나와있는 input 만으로 생각해본다면 생각하기 어려울 듯싶다.

적어도 2번 case에 대해서 input 하나를 추가하였으면 한다.

 

1. 트리를 형성하는 방법은 2차원 배열 Tree를 사용한다.

     Tree [cur][0] = cur 노드의 left-child 노드

     Tree [cur][1] = cur 노드의 right-child 노드

     위와 같이 설정해주면 된다.

 

2. root 노드를 찾는 방법은 1번 노드부터 N번 노드까지의 트리 높이 중에 가장 큰 경우를 찾는다.

     recursive 하게 child 노드로 이동하면서 노드가 존재하지 않을 때까지 이동할 경우 해당 위치의 depth를 

     반환함으로써 그러한 depth 중에 가장 큰 값들 중에 가장 큰 경우에 대한 노드가 root 노드가 된다.

 

 

이를 코드로 작성하면 다음과 같다.

 

int f(int cur, int level) {
    if(cur == -1)
        return level;
    if(cur != -1) { // 왼쪽 트리에서의 최대 레벨과 오른쪽 트리에서의 최대레벨 중 최댓값
        return max(f(Tree[cur][0], level + 1), f(Tree[cur][1], level + 1));
    }
}

 

 

3. 중위 운행을 통해 level, position을 배치하는 방법은 다음과 같다.

    먼저 position 부여를 위해서 전역 변수 pos를 이용한다.

    recursive 하게 tree를 이동하면서 아래의 그림과 같이 pos 값을 부여할 수 있다.

 

이를 코드로 작성하면 다음과 같다.

 

// infix-order
void tree_traversal(int cur, int level) {
    if(cur != -1) {
        tree_traversal(Tree[cur][0], level + 1); // 왼쪽 자식노드로 이동
        tree_level[cur] = level, tree_position[cur] = ++pos; // 위치와 레벨을 부여
        tree_traversal(Tree[cur][1], level + 1); // 오른쪽 자식노드로 이동
    }
}

 

 

4, 5는 level, position 값을 가지고 간단하게 구현해주면 끝이다.

 

 

Solution Code

 

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <string>
#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#define endl '\n'

using namespace std;

vector<int> v[10001];
int Tree[10001][2];
int tree_level[10001], tree_position[10001];
int pos; // 위치 부여를 위한 전역변수

int find_max_level(int cur, int level) {
	if (cur == -1) {
		return level;
	}
	if (cur != -1) {
		return max(find_max_level(Tree[cur][0], level + 1), 
			find_max_level(Tree[cur][1], level + 1));
	}
}

void tree_traversal(int cur, int level) {
	if (cur != -1) {
		tree_traversal(Tree[cur][0], level + 1);
		tree_level[cur] = level, tree_position[cur] = ++pos;
		tree_traversal(Tree[cur][1], level + 1);
	}
}

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

	int root, cur, max_level, left, right, N, level, width;

	cin >> N;
	for (int i = 1; i <= N; i++) {
		cin >> cur >> left >> right;
		Tree[cur][0] = left;
		Tree[cur][1] = right;
	}
	
	max_level = root = -1;
	for (int i = 1; i <= N; i++) {
		if ((level = find_max_level(i, 0)) > max_level) {
			max_level = level;
			root = i;
		}
	}

	tree_traversal(root, 1);

	for (int i = 1; i <= N; i++) {
		v[tree_level[i]].push_back(tree_position[i]);
	}

	for (int i = 1; i <= max_level; i++)
		sort(v[i].begin(), v[i].end());

	width = level = -1;
	for (int i = 1; i <= max_level; i++) {
		if (v[i].size() == 1) {
			if (1 > width) {
				width = 1;
				level = i;
			}
		}
		else if (v[i].size() >= 2) {
			if (v[i][v[i].size() - 1] - v[i][0] + 1 > width) {
				width = v[i][v[i].size() - 1] - v[i][0] + 1;
				level = i;
			}
		}
	}

	cout << level << " " << width;

	return 0;
}