[BAEKJOON] 2250번 트리의 높이와 너비

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

2250번: 트리의 높이와 너비

처음 문제를 보자마자 그래프가 나오길래 그래프 탐색 방법을 떠올렸다.

접근 방법은 차례대로 인덱싱하는 방향이길래 왼쪽부터 차례대로 인덱싱할수 있도록 DFS방식으로 접근해봤다.

또한 각 레벨에서의 너비를 구해야하는데, 탐색할때마다 인덱스를 1부터 시작해서 하나씩 증가시켜주며(어차피 왼쪽에서 부터 차례대로 인덱싱 할거니까),  각 레벨의  low, high 배열을 갱신시켜서 왼쪽 끝과 오른쪽 끝을 저장했다.

너무 잘 풀었다고 생각하고 제출하니까 90% 쯤에서 틀렸다고 결과가 나왔다

진짜 왜 틀렸지,,,

문제를 처음부터 꼼꼼히 다시 읽어 봤는데 너무도 당연하게 1부터 시작해서 왼쪽 자식, 오른쪽 자식 순으로 진행하는줄알았던,,

루트노드에 1이 아닌, 다른값도 올 수 있다는 점이었다,,!

그래서 나는 루트노드를 판별하기위해서  조회되는 노드가 1개뿐인 노드를 루트 노드로 선정하고 다시 풀었다.

결과는

성공!

소스코드

#include <iostream>
#include <vector>
#include <algorithm>
#define MAX 10001
using namespace std;

int n, res, low[MAX], high[MAX], judge[MAX], col;
pair<int, int> v[MAX];
//각 노드의 열 위치
void dfs(int node, int level) {
	if (node == -1) return;
	dfs(v[node].first, level + 1);
	low[level] = min(low[level], col);
	high[level] = max(high[level], col++);
	dfs(v[node].second, level + 1);
}

//너비가 가장 넓은 레벨과 그 레벨의 너비 구하기
int main(){
	cin >> n;
	for (int i = 1; i <= n; i++) {
		int node, left, right;
		cin >> node >> left >> right;
		v[node] = { left, right };
		judge[node]++;
		if (v[node].first != -1) judge[v[node].first]++;
		if (v[node].second != -1) judge[v[node].second]++;
		low[i] = 987654321;
	}
	int root = 0;
	for (int i = 1; i <= n; i++) {
		if (judge[i] == 1) root = i;
	}
	col = 1;
	dfs(root, 1);
	
	res = high[1] - low[1] + 1;
	int cnt = 1;
	for (int i = 2; i <= n; i++) {
		if (res < high[i] - low[i] + 1) {
			res = high[i] - low[i] + 1;
			cnt = i;
		}
	}
	cout << cnt << " " << res;
}

 

이번에는 문제 지문을 꼼꼼하게 읽어 보는 것의 중요성을 느끼게 되었다 ㅎㅎ