백준 - 2250 트리의 높이와 너비

문제

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

2250번: 트리의 높이와 너비

트리의 각 레벨의 양 끝 노드간의 거리 중 최댓값을 구하는 문제였다.

 

문제 풀이

처음에는 트리 노드에 달려 있는 노드들의 합으로 위치를 계산하려고 했는데, 중위순회를 하면 순회하는 순서가 위치가 될 것 같아서 다시 풀었다.

 

1. 1번 노드의 parent를 계속 거슬러 올라가 루트 노드를 찾는다.
2. 루트노드에서부터 중위순회를 돌려 각 노드의 위치를 찾는다.
3. 트리를 레벨 별로 순회를 해서 해당 레벨의 양 끝에 있는 노드를 찾는다.
4. 각 레벨 별 너비를 구하고 가장 긴 길이와 해당 길이일 때의 레벨을 찾는다.

 

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <iostream>
#include <cstring>
#include <algorithm>
#include <vector>
#include <queue>

using namespace std;

typedef struct Node {
	int parent;
	int left;
	int right;
}node;

vector<node> T;
vector<int> nodePosition;
vector<pair<int, int>> levelPosition;
int N;
int cnt = 1;
int maxWidth = 0;
int minLevel = 987654321;
int rootNode;

void findRootNode(int node) {	
	if (T[node].parent != -1) {
		findRootNode(T[node].parent);
	}
	else {
		rootNode = node;
		return;
	}
}

void traversal(int node) {
	if (node == -1) return;
	traversal(T[node].left);
	nodePosition[node] = cnt;
	cnt++;
	traversal(T[node].right);
}


void printNodePosition() {
	for (int i = 1; i <= N; i++) {
		printf("%d ", nodePosition[i]);
	}
	printf("\n");
}

void findLevelWidth(int root) {
	queue<pair<int,int>> q;
	int level = 1;
	q.push({ root, level });
	levelPosition = vector<pair<int, int>>(2, { 987654321, -1 }); //0, 1레벨은 하지 않음

	while (!q.empty()) {
		int nowNode = q.front().first;
		int nowLevel = q.front().second;
		q.pop();

		if (levelPosition.size() <= nowLevel) levelPosition.push_back({ 987654321, -1 });
		if (levelPosition[nowLevel].first > nodePosition[nowNode]) {
			levelPosition[nowLevel].first = nodePosition[nowNode];
		}
		if (levelPosition[nowLevel].second < nodePosition[nowNode]) {
			levelPosition[nowLevel].second = nodePosition[nowNode];
		}

		if (T[nowNode].left != -1) q.push({ T[nowNode].left, nowLevel + 1 });
		if (T[nowNode].right != -1) q.push({ T[nowNode].right, nowLevel + 1 });		
	}

	for (int i = 1; i < levelPosition.size(); i++) {	
		int nowWidth = levelPosition[i].second - levelPosition[i].first+1;
		//printf("%d level nowLevel width: %d\n", i, nowWidth);
		if (maxWidth < nowWidth) {
			maxWidth = nowWidth;
			minLevel = i;
		}		
	}
}

int main() {

	scanf("%d", &N);

	T = vector<node>(N + 1, { -1,0,0 });
	nodePosition = vector<int>(N + 1);

	for (int i = 0; i < N; i++) {
		int a, b, c;
		scanf("%d %d %d", &a, &b, &c);
		T[a].left = b;
		T[a].right = c;
		if(b!=-1) T[b].parent = a;
		if(c!=-1) T[c].parent = a;
	}

	findRootNode(1);

	traversal(rootNode);
	//printNodePosition();
	findLevelWidth(rootNode);

	printf("%d %d", minLevel, maxWidth);

	return 0;
}