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

문제 요약

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

문제 분류

• 그래프 이론
• 그래프 탐색
• 트리
• DFS

문제 풀이

트리를 만들어서 DFS하여 풀었다. 이진트리였기에 이전처럼 multimap을 사용하지 않고, pair<int,int>의 배열로 선언하여 트리 구조를 만들었다. 루트노드부터 트리를 탐색할 때에 LDR방식을 통해 각 노드마다 열 번호를 붙혀주었으며, 같은 높이의 노드에 대해 가장 왼쪽과 가장 오른쪽 노드의 값을 if문으로 갱신해주었다. L[level]은 level 높이에서 가장 왼쪽에 있는 열 번호이고, R[level]은 level 높이에서 가장 오른쪽에 있는 열의 번호이다. 또한 트리의 높이는 level의 최대치이므로 탐색중에도 갱신해준다.

이렇게 만들어진 L배열과 R배열을 1번 높이부터 최대치 높이까지 돌면 된다. 해당 for문 안에서 R[i] - L[i] + 1이 결국 i번째 높이의 너비가 되므로 해당 값의 최대치와 그 높이를 갱신하고, 출력하면 된다.

루트노드가 1이 아닐 때와, 입력 순서가 순서대로 되지 않을 경우, 편향 이진트리인 경우 등의 경우도 테스트 케이스로 주어지므로 유의하여야 한다. 이 부분만 디테일하게 고친다면 통과할 것이다.

풀이 코드

#include <stdio.h>
#include <iostream>
#include <algorithm>

using namespace std;

int n, num[10000], cnt = 1;
pair<int, int> v[10000];
int L[10001], R[10001], s;

void dfs(int idx, int level) {
	if (v[idx].first >= 0) dfs(v[idx].first, level + 1);
	num[idx] = cnt++;
	if (num[idx] < L[level] || !L[level]) L[level] = num[idx];
	if (num[idx] > R[level] || !R[level]) R[level] = num[idx];
	if (v[idx].second >= 0) dfs(v[idx].second, level + 1);
	if (level > s) s = level;
}

int main() {
	int in1, in2, in3, res1 = 0, res2 = 0, root = 0;
	bool go;
	cin >> n;
	for (int i = 0; i < n; i++) {
		scanf("%d%d%d", &in1, &in2, &in3);
		v[in1 - 1] = { in2 - 1,in3 - 1 };
	}
	while (true) {
		go = true;
		for (int i = 0; i < n; i++) {
			if (v[i].first == root || v[i].second == root) {
				root = i;
				go = false;
				break;
			}
		}
		if (go) break;
	}
	dfs(root, 1);
	for (int i = 1; i <= s; i++) {
		in1 = L[i];
		in2 = R[i];
		if (in2 - in1 + 1 > res2) {
			res2 = in2 - in1 + 1;
			res1 = i;
		}
	}
	cout << res1 << " " << res2;
	return 0;
}