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

 

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>

using namespace std;

const int MaxNode = 10001;
int x = 1, maxY = 0;
pair<int, int> nodes[MaxNode];	//노드들을 받아온다.
vector<int> pos[MaxNode];	//노드들의 위치를 저장한다.
bool visited[MaxNode];	//노드를 갔나의 표시

void MidCycle(int y, int curr);

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

	int n, m, level = 1, length = 1;

	cin >> n;

	for (int i = 0; i < n; i++)
	{
		int temp1, temp2, temp3;
		cin >> temp1 >> temp2 >> temp3;
		nodes[temp1] = make_pair( temp2, temp3 );
		visited[temp2] = true;	//자식인 것은 true
		visited[temp3] = true;
	}

	for (int i = 1; i <= n; i++)	//루트노드의 숫자를 검색
	{
		if (!visited[i])
		{
			m = i;	//루트 노드의 수
			visited[i] = false;	//나중에 방문용으로 쓰기위해 false로 바꿈
		}
		else visited[i] = false;
	}

	MidCycle(1, m);	//루트노드부터 시작

	for (int i = 2; i <= maxY; i++)	//루트노드는 너비가 1이므로 생략
	{
		int minX = pos[i][0], maxX = pos[i][pos[i].size() - 1];	//작은 x좌표, 큰 x좌표

		if (length < (maxX - minX + 1))	//같지않아야하고 무조건 클때만
		{
			level = i;	//현재 레벨저장
			length = maxX - minX + 1;	//제일 긴 너비
		}
	}

	cout << level << " " << length;
}

void MidCycle(int y, int curr)	// (왼쪽 자식) (루트) (오른쪽 자식)
{
	if (nodes[curr].first != -1)	//왼쪽을 계속 들어갔다가
		MidCycle(y + 1, nodes[curr].first);

	if (!visited[curr])	//나오면서 하나씩 저장
	{
		pos[y].push_back(x);
		visited[curr] = true;
		x += 1;

		maxY = max(maxY, y);	//최하단 높이
	}

	if (nodes[curr].second != -1)	//나오는데 오른쪽 자식이 있으면 들어간다.
		MidCycle(y + 1, nodes[curr].second);

	if (!visited[curr])	//나오면서 하나씩 저장
	{
		pos[y].push_back(x);
		visited[curr] = true;
		x += 1;

		maxY = max(maxY, y);
	}
}

 

풀이

- 현재노드의 좌측과 우측값을 잘 저장한다.

- 중위 순회로 탐색을 해야한다.

- 중위 순회로 탐색을 할시 왼쪽을 기준으로 순회를 할 수 있다.

- 왼쪽의 최하단 노드를 순서대로 x를 하나씩 중첩해나간다.

- 해당 높이에 있는 x값들을 저장한다. 저장할 때 어차피 왼쪽부터 하나씩 넣기때문에 오름차순으로 값이 들어감.

- 높이별로 가장 좌측 [0] ~ [size()]의 너비를 측정한다.

- 같을 경우는 처음 큰 수일때만 넣어주어 동일 크기일때 너비를 넣지않게 하여 최소높이의 최대너비가 나오게 한다.

 

주의사항

- 루트 노드가 1이 아닐 경우가 있다.... 그래서 꼭 루트노드를 검사해야된다.