[백준/BOJ] 백준 2250번 : 트리의 높이와 너비

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

2250번: 트리의 높이와 너비

 

노드별로 왼쪽 자식 노드의 서브트리의 크기와 오른쪽 자식 노드의 서브트리의 크기를 구하고 이를 이용해 노드별로 어떤 열 번호에 속하는지 구한다. 그리고 루트노드부터 아래로 탐색해 나아가며, 레벨별 속하는 노드들의 열 번호를 저장해 놓고, 이를 통해 각 레벨의 너비를 확인하는 방법으로 문제를 해결했다.

 

코드

#include <iostream>
#include <algorithm>
#include <vector>
#include <set>
using namespace std;

int n;
vector<int> parent(10005, 0);
vector<int> left_child(10005, 0);
vector<int> right_child(10005, 0);
int root;
vector<int> left_subtree_size(10005, 0);
vector<int> right_subtree_size(10005, 0);
int result1 = -1;
int result2 = -1;
vector<int> col_num(10005, 0); //해당 노드의 열 번호
set<int> level_col[10005]; //[해당 레벨] = (해당 레벨 노드들의 열 번호들)

//here노드의 왼쪽 서브트리의 크기와, 오른쪽 서브트리의 크기 구하기
int check_subtree_size(int here) {

	if (left_child[here] != -1) {
		left_subtree_size[here] = check_subtree_size(left_child[here]);
	}

	if (right_child[here] != -1) {
		right_subtree_size[here] = check_subtree_size(right_child[here]);
	}

	return left_subtree_size[here] + right_subtree_size[here] + 1;
}

//here노드의 열 번호 구하기
void check_col_num(int here, int left_range, int right_range) {

	int here_col_num = left_range + left_subtree_size[here];
	col_num[here] = here_col_num;

	if (left_child[here] != -1) {
		check_col_num(left_child[here], left_range, here_col_num - 1);
	}

	if (right_child[here] != -1) {
		check_col_num(right_child[here], here_col_num + 1, right_range);
	}
}

//레벨별 속하는 노드들의 열 번호 저장
void check_level_col(int here, int level) {

	level_col[level].insert(col_num[here]);

	if (left_child[here] != -1) {
		check_level_col(left_child[here], level + 1);
	}

	if (right_child[here] != -1) {
		check_level_col(right_child[here], level + 1);
	}

}

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

	cin >> n;

	for (int i = 0; i < n; i++) {
		int node_num, left_num, right_num;
		cin >> node_num >> left_num >> right_num;

		left_child[node_num] = left_num;
		right_child[node_num] = right_num;

		if (left_num != -1) {
			parent[left_num] = node_num;
		}

		if (right_num != -1) {
			parent[right_num] = node_num;
		}
	}

	for (int i = 1; i <= n; i++) {
		if (parent[i] == 0) { //부모노드가 없다면, 루트노드
			root = i;
		}
	}

	check_subtree_size(root);
	check_col_num(root, 1, n);
	check_level_col(root, 1);

	for (int i = 1; i <= n; i++) {

		if (level_col[i].size() == 0) { //해당 레벨의 노드가 더이상 없을때
			break;
		}

		int left_col = *(level_col[i].begin());
		int right_col = *(--(level_col[i].end()));
		int width = right_col - left_col + 1;

		if (width > result2) { //더 큰 너비를 발견했을때
			result1 = i;
			result2 = width;
		}
	}

	cout << result1 << " " << result2 << "\n";

	return 0;
}