BOJ (C/C++) 2250번: 트리의 높이와 너비

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

2250번: 트리의 높이와 너비

---

풀이

입력 받은 후 루트를 찾고, 트리를 중위순회하며 루트 값을 레벨에 따라 나눠서 저장했다.

 

탐색되는 순서가 노드의 가로 위치이므로 cnt로 위치를 세어주었다.마찬가지로 Height 벡터에 레벨 별로 나뉘어 저장된 노드들도 왼쪽부터 순서대로 저장되어 있으므로 (마지막에 저장된 노드)-(처음 저장된 노드)의 값이 해당 레벨에서의 최대 넓이이다.

 

 

< 주의할 점 >

- 입력은 순서대로 들어오지 않을 수도 있다. 즉, 루트가 언제 들어올지 모른다.

- 입력 받을 때 각 노드의 레벨은 알 수 없다.

- 모든 레벨에 노드가 1개씩만 있을 때 출력되는 레벨은 1이다.

---

코드

#include <stdio.h>
#include <vector>
using namespace std;

// Tree[node][3] = { 왼쪽 자식, 오른쪽 자식, 루트 }
int Tree[10001][3];
vector <int> Height[10001];


// 중위탐색하여 노드의 가로 위치를 레벨 별로 저장
int cnt = 1;
void Search(int start, int lev) {
	int lc = Tree[start][0], rc = Tree[start][1];

	if (lc != -1) Search(lc, lev + 1);
	Height[lev].push_back(cnt++);
	if (rc != -1) Search(rc, lev + 1);
}

void Classification(int N) {
	// 모든 레벨에 노드가 1개씩 있을 경우엔 max_lev이 1이므로 초기값으로 지정해줌
	int lev = 1, max = 0, max_lev = 1;

	// 마지막 레벨까지 탐색
	while (Height[lev].size() != 0 && lev <= 10000) {

		// Height 벡터에 왼쪽에 위치한 노드부터 순서대로 들어오므로 처음과 마지막에 들어온 노드의 너비를 측정
		int size = Height[lev].size(), width = Height[lev][size - 1] - Height[lev][0];

		if (width > max) max_lev = lev, max = width;
		lev++;
	}

	printf("%d %d", max_lev, max + 1);
}

int main() {
	int N;
	int r, lc, rc, root;

	// input
	scanf("%d", &N);
	for (int i = 0; i < N; i++) {
		scanf("%d %d %d", &r, &lc, &rc);

		// Tree[3] = { 왼쪽 자식, 오른쪽 자식, 루트 }
		Tree[r][0] = lc, Tree[r][1] = rc;
		Tree[lc][2] = Tree[rc][2] = r;
	}

	// root인 노드는 Tree[2]값에 아무것도 들어오지 않으므로 0
	while (Tree[++root][2] != 0);

	Search(root, 1);
	Classification(N);

	return 0;
}