취미로 코딩하기

※ 글쓴이는 취미로 코딩을 익혀보는 사람이라 정확하지 않은 내용을 담고 있을 수 있다 ※

이번에 볼 문제는 백준 2250번 문제인 트리의 높이와 너비이다.
문제는 아래 링크를 확인하자.

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

중위순회(inorder traversal)을 이용해 주어지는 이진트리의 노드들을 x좌표순으로 나열해나가면서, 각 깊이의 최소 x좌표와 최대 x좌표를 관리하는 코드를 작성해 문제를 해결하자.

주어진 트리의 루트노드는 "어떤 노드의 자식노드로 쓰인 적이 없는 노드"를 찾는 것으로 빠르게 발견해낼 수 있다.

아래는 제출한 소스코드이다.

#include <iostream>
using namespace std;

int idx = 1;
int N, root;
int G[10001][2];
int level[10001][2];
bool is_child[10001];

void dfs(int cur, int lv) {
	if (G[cur][0] > 0) dfs(G[cur][0], lv + 1);
	if (level[lv][0] == 0) level[lv][0] = level[lv][1] = idx++;
	else level[lv][1] = idx++;
	if (G[cur][1] > 0) dfs(G[cur][1], lv + 1);
}

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

	cin >> N;
	for (int i = 0; i < N; i++) {
		int x; cin >> x;
		int& l = G[x][0], & r = G[x][1]; cin >> l >> r;
		if (l > 0) is_child[l] = 1;
		if (r > 0) is_child[r] = 1;
	}

	for (int i = 1; i <= N; i++) {
		if (!is_child[i]) root = i;
	}
	
	dfs(root, 1);

	int mx = -1, lv = -1;
	for (int i = 1; i <= N; i++) {
		if (!level[i][0]) break;
		int diff = level[i][1] - level[i][0] + 1;
		if (diff > mx) mx = diff, lv = i;
	}

	cout << lv << ' ' << mx;
}