[백준 2250] 트리의 높이와 너비 (C++)

이 문제는 트리를 표현하고, 각 노드의 번호를 계산해야, 너비가 가장 넓은 레벨과 그 너비를 구할 수 있다.

트리는 그래프의 일종이므로 인접 행렬이나 인접 리스트로 표현해야한다. 문제에서, 노드간의 연결 관계 보다는, 트리를 탐색해가며 답을 구하는 것에 초점이 맞춰져 있다. 따라서, 인접 리스트로 트리를 표현하는 것이 문제를 푸는데 유리할 것이다.

인접 행렬은 노드 갯수 $N$이 $10,000$이하라 공간복잡도 $O(N^2)$으로는 400MB정도로 메모리 초과가 발생할 것이다.

따라서, 인접 리스트로 표현하는 것이 일반적이겠지만, 우리는 트리가 이진 트리라는 것을 안다. 즉, 자식이 왼쪽과 오른쪽으로 최대 2개만 존재한다는 것을 안다는 의미이다. 따라서, i번째 노드의 왼쪽 자식을 lc[i]에 저장하고 오른쪽 자식을 rc[i]에 저장하는 방식으로 공간복잡도 $O(N)$에 트리를 표현할 수 있다.

추가로, 우리는 루트가 무엇이 될 지 모른다. 따라서, 루트에 대한 정보도 기록해두면, 나중에 쉽게 찾을 수 있을 것이다. i번째 노드의 부모를 pr[i]에 저장해보자.

$2$ ~ $N + 1$번째 입력은 부모 p, 왼쪽 자식 l, 오른쪽 자식 c가 차례로 주어지는데 자식이 -1이 아니면 lc[p] = l이고 pr[l] = p 혹은 rc[p] = r이고 pr[r] = p로 부모 자식 관계를 표현해 줄 수 있다.

이 때, 루트는 유일하게 부모가 없을 것이므로, pr값은 $0$이 된다.

이제, 루트를 알아냈으므로, 열 번호를 구할 방법을 고민해보자.
설명하기 앞서, 조건 3을 다시 살펴보자. 왼쪽 서브 트리의 노드들은 해당 서브 트리의 루트 노드보다 왼쪽에, 오른쪽 서브 트리의 노드들은 해당 서브 트리의 루트 노드보다 오른쪽에 존재한다고 기술되어 있다.

따라서, 우리는 트리 순회 기법 중 inorder를 통해 열 번호를 구할 수 있다는 것을 알 수 있다.

이제 정답을 구해야하는데, 이는 너비가 가장 넓은 레벨과 그 때의 너비를 구해야 한다. 즉, 레벨별로 최대 너비를 구해봐야한다는 소리인데, 이는 레벨 순회로 접근해야 한다는 소리가 된다. 해당 레벨에서 가장 왼쪽 노드의 열 번호와 가장 오른쪽 노드의 열 번호의 차 + 1이 너비가 되기 때문에, 이를 바탕으로 코드를 짜보자.

#include <bits/stdc++.h>
using namespace std;

int n, counter = 1, w, mxLevel;
int lc[10'001], rc[10'001], pr[10'001], c[10'001];

void inorder(int cur) {
	if (lc[cur]) inorder(lc[cur]);
	c[cur] = counter++;
	if (rc[cur]) inorder(rc[cur]);
}

void levelorder(int root) {
	queue<int> q;
	queue<int> wq;
	q.push(root);
	int level = 1;

	while (1) {
		int nxtW = c[q.back()] - c[q.front()] + 1;
		if (w < nxtW) {
			w = nxtW;
			mxLevel = level;
		}
		while (!q.empty()) {
			int cur = q.front();
			q.pop();

			if (lc[cur]) wq.push(lc[cur]);
			if (rc[cur]) wq.push(rc[cur]);
		}

		if (wq.empty()) break;

		q = wq;
		wq = queue<int>();
		level++;
	}
}

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

	cin >> n;
	for (int i = 0; i < n; i++) {
		int p, l, r;
		cin >> p >> l >> r;
		if (l != -1) {
			lc[p] = l;
			pr[l] = p;
		}
		if (r != -1) {
			rc[p] = r;
			pr[r] = p;
		}
	}

	int root = find(pr + 1, pr + n + 1, 0) - pr;
	inorder(root);
	levelorder(root);
	cout << mxLevel << " " << w;
}