[BOJ] 2250번: 트리의 높이와 너비 (c++)

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

2250번: 트리의 높이와 너비

 

중위 순회로 레벨별 최소 인덱스, 최대 인덱스 구하기 --> 최대 차이 구하기

#include <iostream>
#include <vector>
#include <limits>
#include <algorithm>

using namespace std;

struct node {
	int parent, left, right;
};
struct level {
	int min, max;
};

int order = 1;
int max_depth;

// parent가 0 인 루트노드 찾기
int find_root(vector<node>& tree)
{
	for (int i = 1; i < tree.size(); ++i)
	{
		if (tree[i].parent == 0)
		{
			return i;
		}
	}
	return 0;
}

// 중위순회로 탐색하며 레벨 별 최소 인덱스, 최대 인덱스 찾기
void dfs_inorder(vector<node> &tree, vector<level> &levels, int n, int depth)
{
	if (n == -1)
	{
		return;
	}

	dfs_inorder(tree, levels, tree[n].left, depth + 1);
	
	order++;
	levels[depth].min = min(levels[depth].min, order);
	levels[depth].max = max(levels[depth].max, order);
	max_depth = max(max_depth, depth);

	dfs_inorder(tree, levels, tree[n].right, depth + 1);
}

// 너비가 최대인 레벨과 그 너비값 구하기
pair<int, int> get_max_level_n_width(vector<level> &levels)
{
	int max_level = 0, max_width = 0;

	for (int i = 1; i <= max_depth; ++i)
	{
		int width = levels[i].max - levels[i].min + 1;
		if (max_width < width)
		{
			max_width = width;
			max_level = i;
		}
	}
	return {max_level, max_width};
}

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

	// 입력
	int N;
	cin >> N;
	vector<node> tree(N + 1);
	for (int i = 0; i < N; ++i)
	{
		int p, l, r;
		cin >> p >> l >> r;
		
		// 자식노드 저장
		tree[p].left = l;
		tree[p].right = r;
		
		// 부모노드 저장
		if (l != -1)
		{
			tree[l].parent = p;
		}
		if (r != -1)
		{
			tree[r].parent = p;
		}
	}

	// 레벨별 <최소 인덱스, 최대 인덱스>를 저장할 벡터 
	vector<level> levels(N + 1, { numeric_limits<int>::max() , 0 });


	// 중위순회로 탐색하며 레벨 별 최소 인덱스, 최대 인덱스 찾기
	dfs_inorder(tree, levels, find_root(tree), 1);
	

	// 너비가 최대인 레벨과 그 너비값 구하기
	pair<int, int> max_p =  get_max_level_n_width(levels);
	cout << max_p.first << ' ' << max_p.second;

	return 0;
}

 

inorder로 탐색한다는 아이디어 자체를 떠올리는 건 어렵지 않았지만, 

세부 사항이 힘들었던 문제 ㅜㅜ

 

 

※ 이 문제를 풀때 유의해야할 사항

1. 루트 노드가 1이 아닐 수 있다.

2. 결국 중요한 것은 depth와 order_index이다. 

 

 

1. 루트 노드가 1이 아닐 수 있다.

루트 노드를 구하는 다양한 방법이 있다. 

  ㄱ. 입력받는 노드들의 개수를 카운팅하여, 가장 적게 들어온 노드 찾기

  ㄴ. 노드 struct에 parent를 추가하여, parent가 0인 노드 찾기

나는 그중에 ㄴ으로 구현하였다.

// parent가 0 인 루트노드 찾기
int find_root(vector<node>& tree)
{
	for (int i = 1; i < tree.size(); ++i)
	{
		if (tree[i].parent == 0)
		{
			return i;
		}
	}
	return 0;
}

 

 

 

2. 결국 중요한 것은 depth와 order_index이다. 

2번은 크게 유의하지 않아도 틀리지는 않는다. 

그래도 문제가 요구하는 바를 명확히 인지하면, 코드가 줄어들 수 있다.

 

임의의 이진트리가 입력으로 주어질 때 너비가 가장 넓은 레벨과 그 레벨의 너비를 출력하는 프로그램을 작성하시오

문제는 너비가 가장 넓은 레벨과 너비를 구하라고 했으므로, 

각 노드의 모든 레벨과 order_index를 저장하고 있을 필요는 없다.

이를 인지하면 dfs_inorder() 함수에서 해주어야 할 역할이 무엇인지 알 수 있다.

// 중위순회로 탐색하며 레벨 별 최소 인덱스, 최대 인덱스 찾기
void dfs_inorder(vector<node> &tree, vector<level> &levels, int n, int depth)
{
    ...

    order++;
    levels[depth].min = min(levels[depth].min, order);
    levels[depth].max = max(levels[depth].max, order);
    max_depth = max(max_depth, depth);

    ...
}

 

그러면 이 다음에 레벨 벡터만 반복문을 돌려서 최대 너비를 찾아내기만 하면 된다.