BOJ 2250 트리의 높이와 너비

www.acmicpc.net/problem/2250

2250번: 트리의 높이와 너비

 

문제를 본 지는 좀 되었는데, 그당시에 뭔소린지 모르겠어서 못 풀었던 문제이다.

이번에 한번 더 보았는데, 너무 쉬운 문제였다.

 

왼쪽의 숫자는 노드의 깊이이고, 아래의 숫자는 inorder탐색을 했을때의 방문순서이다!!

 

따라서 이 문제는 그냥 노드의 깊이마다 inorder탐색을 제일 처음 만난 친구와 제일 늦게 만난 친구의 탐색순서의 차이를 출력하면 되는 문제이다.

 

#include <bits/stdc++.h>
using namespace std;
typedef pair<int, int> ii;
int cnt = 1;
vector<ii> lr;
vector<vector<int> > edge;

void dfs(int now, int d) {
	if (now == -1) return;
	
	dfs(edge[now][0], d+1);
	if (lr[d].first == 0) lr[d].first = cnt;
	else lr[d].second = cnt;
	cnt++;
	dfs(edge[now][1], d+1);
}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);
	
	int n; cin >> n;
    
    //lr[i].first, seconnd : 깊이 i에서의 inorder값 최소, 최대를 가진다.
	lr.resize(n + 1, ii(0,0));
	edge.resize(n + 1);
	vector<int> in(n + 1);
	for (int i = 1; i <= n; i++) {
		int a, b, c;
		cin >> a >> b >> c;
		edge[a].push_back(b);
		edge[a].push_back(c);
		if (b != -1)
			in[b]++;
		if (c != -1)
			in[c]++;
	}
    
    //루트가 어딘지 모름
	for (int i = 1; i <= n; i++) {
		if (in[i] == 0) {
			dfs(i, 1);
			break;
		}
	}
    
    //이 문제는 단순히 inorder를 돌리면서 번호를 매기고,
    //각 깊이에서의 inorder값의 max - min이다.
	int ans = 1, lv = 1;
	for (int i = 1; i <= n; i++) {
		if (lr[i].second - lr[i].first + 1 > ans) {
			ans = lr[i].second - lr[i].first + 1;
			lv = i;
		}
	}

	cout << lv << " " << ans;
	return 0;
}

 

일반적인 문제는 노드에 탐색순서를 저장하는데, 이 문제는 그 노드의 깊이에다가 탐색순서를 저장해주고, 제일 빠른 친구와 제일 늦는 친구의 차이만 구해주면 되는 문제이다.

 

루트가 1이라는 보장이 없다... 이것때문에 틀리는 일이 없기를(나는 틀렸다)