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

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

2250번: 트리의 높이와 너비

 

이 문제는 트리를 중위순회 하는 순서대로 index 번호를 부여하고 트리 height 별로 index 최대 값과 최소 값을 차의 최대값, 즉 너비의 최대값을 구하는 문제다.

문제 자체는 재귀적 중위 순회를 통해 높이별 min, max idx값을 갱신하여 간단하게 풀 수 있다.

다만 이 문제에서는 루트 정보가 주어지지 않았기 때문에 루트 노드도 직접 구해줘야한다.

#include <iostream>
#include <vector>

#define min(a,b) a<b?a:b
#define max(a,b) a>b?a:b

using namespace std;

int n, idx = 1;
//최악의 경우 높이가 10000인 트리가 될 수 있으므로,
//배열의 최대값을 10001로 선언
int tree[10001][2];
int parent[10001];
int min_val[10001];
int max_val[10001];

void input() {
	int cur, left, right;
	cin >> n;
	
    //부모 노드를 자기 자신으로 초기화
	for (int i = 1; i <= n; i++) {
		parent[i] = i;
	}

	for (int i = 1; i <= n; i++) {
		cin >> cur >> left >> right;
		tree[cur][0] = left;
		tree[cur][1] = right;
		//루트 노드를 찾기 위해 부모 노드 정보 저장
		parent[left] = cur;
		parent[right] = cur;
	}
}

int find_root() {
	//부모노드가 자기 자신인 경우, 해당 노드가 루트 노드
	for (int i = 1; i <= n; i++) {
		if (parent[i] == i) return i;
	}
}

//중위 순회로 idx 갱신
void inorder(int node, int height) {
	if (node < 0) return;
	
    //왼쪽 자식 노드
	if (tree[node][0] > 0) inorder(tree[node][0], height + 1);
    //해당 노드의 idx값을 해당 height의 min, max val과 비교, 갱신
	min_val[height] = min(min_val[height], idx);
	max_val[height] = max(max_val[height], idx);
	++idx;
    //오른쪽 자식 노드
	if (tree[node][1] > 0) inorder(tree[node][1], height + 1);
}

void solution() {
	int root;
	input();
	root = find_root();
	for (int i = 1; i <= n; i++) min_val[i] = 1e5;
	inorder(root, 1);

	int max_width = 0;
	int max_width_height;
    //height 별로 max_val - min_val + 1값 확인 및 갱신
	for (int i = 1; i <= n; i++) {
		if (max_width < max_val[i] - min_val[i] + 1) {
			max_width = max_val[i] - min_val[i] + 1;
			max_width_height = i;
		}
	}
	cout << max_width_height << ' ' << max_width;
}

int main() {
	ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
	solution();

	return 0;
}

메모리: 2216 kb

시간: 4 ms