백준 2250 트리의 높이와 너비

#define _CRT_SECURE_NO_WARNINGS
#include <cstdio>
#include <algorithm>
#include <vector>
#include <queue>
#include <stack>
#include <utility>

using namespace std;

class TreeNode {
public:
	int data;
	int rowNum;
	pair<int, int> connections;
	TreeNode() {
		data = 0;
	}
	TreeNode(int data) : data(data) {}
};

int main() {
	int size;
	scanf("%d", &size);
	vector<TreeNode*> treenodeVector;

	treenodeVector.push_back(new TreeNode(0));
	for (int i = 1; i <= size; i++) {
		treenodeVector.push_back(new TreeNode(i));
	}
	int nodeNum, left, right;
	for (int i = 1; i <= size; i++) {
		scanf("%d %d %d", &nodeNum, &left, &right);
		treenodeVector[nodeNum]->connections = make_pair(left, right);
	}
	//
	int root = 0;
	vector<bool> hasParent(size + 1, false);
	for (int i = 1; i <= size; i++) {
		if (treenodeVector[i]->connections.first != -1) hasParent[treenodeVector[i]->connections.first] = true;
		if (treenodeVector[i]->connections.second != -1)hasParent[treenodeVector[i]->connections.second] = true;
	}
	for (int i = 1; i <= size; i++) {
		if (hasParent[i] == false) {
			root = i;
			break;
		}
	}
	//
	int static_rowNum = 1;
	stack<int> dfsSearchStack;
	dfsSearchStack.push(-1);
	int nowNode = root;
	
	while(true) {
		while (nowNode != -1) {
			dfsSearchStack.push(nowNode);
			nowNode = treenodeVector[nowNode]->connections.first;
		}
		nowNode = dfsSearchStack.top();
		dfsSearchStack.pop();

		if (dfsSearchStack.empty()) break;

		treenodeVector[nowNode]->rowNum = static_rowNum;
		static_rowNum++;
		nowNode = treenodeVector[nowNode]->connections.second;
	} 
	//
	queue<int> bfsSearchQueue;
	nowNode = root;
	bfsSearchQueue.push(nowNode);
	bfsSearchQueue.push(0);
	int minNum_init = 100000;
	int minNum = minNum_init, maxNum=0;
	int maxDist = 0;
	int maxDistLevel = 1;
	int nowLevel = 1;
	while (true) {
		nowNode = bfsSearchQueue.front();
		bfsSearchQueue.pop();
		if (nowNode == 0) {
			if (maxDist < maxNum - minNum + 1) {
				maxDist = maxNum - minNum + 1;
				maxDistLevel = nowLevel;
			}
			minNum = minNum_init;
			maxNum = 0;
			if (bfsSearchQueue.empty()) break;
			bfsSearchQueue.push(0);
			nowLevel++;
			continue;
		}
		if (bfsSearchQueue.empty()) break;
		minNum = min(minNum, treenodeVector[nowNode]->rowNum);
		maxNum = max(maxNum, treenodeVector[nowNode]->rowNum);

		int left = treenodeVector[nowNode]->connections.first;
		if (left != -1) {
			bfsSearchQueue.push(left);
		}
		int right = treenodeVector[nowNode]->connections.second;
		if (right != -1) {
			bfsSearchQueue.push(right);
		}

	}
	printf("%d %d\n", maxDistLevel, maxDist);
	return 0;
}

1. 중위탐색으로 노드에 번호를 매기고(TreeNode.rowNum)

2. BFS로 레벨순서대로 탐색하며 너비를 계산한다

제일 어려웠던게

1 -1 -1

1 2 3 

2 -1 -1

3 -1 -1

이 두가지 케이스가 

하나가 맞으면 하나가 오류나고

하나고 오류나면 하나가 맞고...

이렇게 서로 번갈아가면서 정답이여서 ㅋㅋㅋ

여기서 한시간 잡아먹었다

아 그리고 루트가 1번인줄 알았는데 아닌 경우가 있어서 또 한번 틀렸다 ㅋㅋ

진짜 아이디어는 금방 떠올렸는데 구현이 너무 오래걸렸다 ㅜㅜ

문제 보자마자

"중위탐색후에 레벨탐색 하면 되겠네!" 

했는데.. 3시간 걸린듯..

그래도 좋은 문제라고 생각한다.

이거 근데 정보올림피아드 고등부 문제다...

예전에 초등부 문제 풀고 뿌듯! 했던거 기억하면

장족의 발전이다.....ㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋ