개요

백준 2250번: 트리의 높이와 너비

• 입력
  첫째 줄에 노드의 개수를 나타내는 정수 N(1 ≤ N ≤ 10,000)이 주어진다. 다음 N개의 줄에는 각 줄마다 노드 번호와 해당 노드의 왼쪽 자식 노드와 오른쪽 자식 노드의 번호가 순서대로 주어진다. 노드들의 번호는 1부터 N까지이며, 자식이 없는 경우에는 자식 노드의 번호에 -1이 주어진다.

• 출력
  첫째 줄에 너비가 가장 넓은 레벨과 그 레벨의 너비를 순서대로 출력한다. 너비가 가장 넓은 레벨이 두 개 이상 있을 때에는 번호가 작은 레벨을 출력한다.

접근 방식

1. 부모 노드보다 왼쪽 서브트리는 무조건 왼쪽에 위치해야하고, 오른쪽 서브트리는 무조건
   오른쪽에 위치해야한다.
   한 열에 하나씩 노드가 존재해야 하므로 중위 순회를 떠올렸다.
2. 따라서 중위 순회방식으로 도달한 노드마다 해당 노드의 레벨과 순서를 벡터에 넣어줬다.

   //중위 순회 방식으로 레벨과 순서저장하는 벡터인 levelAndWidth에 푸시해준다.
   void InOrder(int Node,int level) {
   	//노드가 -1이면 끝이므로  retunr
   	if (Node == -1) return;
   	//왼쪽 자식으로 재귀
   	InOrder(leftChildren[Node],level+1);
   	// 노드에 도달했다면 level에 order값을 증가시켜서 push해줌
   	levelAndWidth[level].push_back(order++);
   	//오른쪽 자식으로 재귀
   	InOrder(rightChildren[Node],level+1);
   }

3. 중위순회가 끝난 후 최대 너비, 최대 너비의 레벨을 갱신하며 답을 출력해준다.

   		//levelAndWidth 탐색하면서
   		for (int i = 1; i < levelAndWidth.size(); i++) {
   			//levelAndWidth[i]가 비어있다면 패스
   			if (!levelAndWidth[i].size()) continue;
   			else {
   				//최대 거리가 i레벨의 최대 너비보다 크거나 같다면 continue
   				//같을때도 continue인건 최대너비 같으면 제일 작은 레벨 반환해야하므로
   				if (maxDist >= levelAndWidth[i].back() - levelAndWidth[i].front() + 1) {
   					continue;
   				}
   				//최대 거리가 더 작으면 갱신
   				maxDist = levelAndWidth[i].back() - levelAndWidth[i].front() + 1;
   				//레벨도 갱신
   				maxDistLevel = i;
   			}
   		}
   		//답 출력
   		cout << maxDistLevel<<" "<<maxDist;

4. 하지만 계속 오답이 나오고 반례를 찾을 수 없어서 검색을 해보니
   루트값을 1로 잡으면 안 되었다.
   문제를 대충 읽다보니 "트리의 레벨은 가장 위쪽에 있는 루트 노드가 1이고"
   이 문구에서 루트 노드가 1이라고 착각해버렸다.
   따라서 루트값을 찾는 함수를 따로 만들어줬다.

   //1값을 기준으로 부모값을거슬러 올라가다 parent가 -1인 최초의 값이 루트임
   int findRoot() {
   	int cur = 1;
   	while (1) {
   		//부모값 저장
   		cur = parents[cur];
   		//부모값이 -1이라면 cur이 루트이므로
   		if (parents[cur] == -1) {
   			//반복문 빠져나옴
   			break;
   		}
   	}
   	//cur리턴
   	return cur;
   }

전체코드

#include<iostream>
#include<vector>

using namespace std;

int parents[10'001];
int leftChildren[10'001];
int rightChildren[10'001];
int N,order=1;
vector<vector<int>> levelAndWidth;

//입려값 받아서 트리 구조 형성
void Input() {
	int parent = 0, leftChild = 0, rightChild = 0;
	fill(parents, parents + 10001, -1);
	fill(leftChildren, leftChildren + 10001, -1);
	fill(rightChildren, rightChildren + 10001, -1);
	levelAndWidth.resize(10001);
	cin >> N;
	for (int i = 0; i < N; i++) {
		cin >> parent >> leftChild >> rightChild;
		leftChildren[parent] = leftChild;
		rightChildren[parent] = rightChild;
		parents[leftChild] = parent;
		parents[rightChild] = parent;
	}
}
//중위 순회 방식으로 레벨과 순서저장하는 벡터인 levelAndWidth에 푸시해준다.
void InOrder(int Node,int level) {
	//노드가 -1이면 끝이므로  retunr
	if (Node == -1) return;
	//왼쪽 자식으로 재귀
	InOrder(leftChildren[Node],level+1);
	// 노드에 도달했다면 level에 order값을 증가시켜서 push해줌
	levelAndWidth[level].push_back(order++);
	//오른쪽 자식으로 재귀
	InOrder(rightChildren[Node],level+1);
}
//1값을 기준으로 부모값을거슬러 올라가다 parent가 -1인 최초의 값이 루트임
int findRoot() {
	int cur = 1;
	while (1) {
		//부모값 저장
		cur = parents[cur];
		//부모값이 -1이라면 cur이 루트이므로
		if (parents[cur] == -1) {
			//반복문 빠져나옴
			break;
		}
	}
	//cur리턴
	return cur;
}
void Solution() {
	//최대 거리
	int maxDist = 0;
	//최대 거리가 저장된 레벨
	int maxDistLevel = 0;
	//루트값 저장
	int root = findRoot();
	//중위순회 시작
	InOrder(root,1);
	//levelAndWidth 탐색하면서
	for (int i = 1; i < levelAndWidth.size(); i++) {
		//levelAndWidth[i]가 비어있다면 패스
		if (!levelAndWidth[i].size()) continue;
		else {
			//최대 거리가 i레벨의 최대 너비보다 크거나 같다면 continue
			//같을때도 continue인건 최대너비 같으면 제일 작은 레벨 반환해야하므로
			if (maxDist >= levelAndWidth[i].back() - levelAndWidth[i].front() + 1) {
				continue;
			}
			//최대 거리가 더 작으면 갱신
			maxDist = levelAndWidth[i].back() - levelAndWidth[i].front() + 1;
			//레벨도 갱신
			maxDistLevel = i;
		}
	}
	//답 출력
	cout << maxDistLevel<<" "<<maxDist;
}

int main() {
	Input();
	Solution();
}

문풀후생

백준 1068:트리 문제 처럼 루트가 꼭 1이나 0이 아닐수도 있다는 걸
늘 염두에두고 트리 문제에 접근해야겠다.
두번째 반복되니 이제 좀 생각을 하겠지