[백준] 트리의 높이와 너비 (2250번)

문제

이진트리를 다음의 규칙에 따라 행과 열에 번호가 붙어있는 격자 모양의 틀 속에 그리려고 한다. 이때 다음의 규칙에 따라 그리려고 한다.

1. 이진트리에서 같은 레벨(level)에 있는 노드는 같은 행에 위치한다.
2. 한 열에는 한 노드만 존재한다.
3. 임의의 노드의 왼쪽 부트리(left subtree)에 있는 노드들은 해당 노드보다 왼쪽의 열에 위치하고, 오른쪽 부트리(right subtree)에 있는 노드들은 해당 노드보다 오른쪽의 열에 위치한다.
4. 노드가 배치된 가장 왼쪽 열과 오른쪽 열 사이엔 아무 노드도 없이 비어있는 열은 없다.

이와 같은 규칙에 따라 이진트리를 그릴 때 각 레벨의 너비는 그 레벨에 할당된 노드 중 가장 오른쪽에 위치한 노드의 열 번호에서 가장 왼쪽에 위치한 노드의 열 번호를 뺀 값 더하기 1로 정의한다. 트리의 레벨은 가장 위쪽에 있는 루트 노드가 1이고 아래로 1씩 증가한다.

아래 그림은 어떤 이진트리를 위의 규칙에 따라 그려 본 것이다. 첫 번째 레벨의 너비는 1, 두 번째 레벨의 너비는 13, 3번째, 4번째 레벨의 너비는 각각 18이고, 5번째 레벨의 너비는 13이며, 그리고 6번째 레벨의 너비는 12이다.

우리는 주어진 이진트리를 위의 규칙에 따라 그릴 때에 너비가 가장 넓은 레벨과 그 레벨의 너비를 계산하려고 한다. 위의 그림의 예에서 너비가 가장 넓은 레벨은 3번째와 4번째로 그 너비는 18이다. 너비가 가장 넓은 레벨이 두 개 이상 있을 때는 번호가 작은 레벨을 답으로 한다. 그러므로 이 예에 대한 답은 레벨은 3이고, 너비는 18이다.

임의의 이진트리가 입력으로 주어질 때 너비가 가장 넓은 레벨과 그 레벨의 너비를 출력하는 프로그램을 작성하시오

입력

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

출력

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

예제 입력 1 복사

19 1 2 3 2 4 5 3 6 7 4 8 -1 5 9 10 6 11 12 7 13 -1 8 -1 -1 9 14 15 10 -1 -1 11 16 -1 12 -1 -1 13 17 -1 14 -1 -1 15 18 -1 16 -1 -1 17 -1 19 18 -1 -1 19 -1 -1

예제 출력 1 복사

3 18

---

어찌저찌 풀다보니 코드가 130줄이 나와버렸다.

문제는 네 가지 조건에 의해 트리를 행과 열로 나뉜 격자에 그릴 때, 너비가 최대가 되는 레벨을 구하는 것이다.

열의 번호는 트리의 left 서브트리 - current 노드 - right 서브트리 순으로 부여한다.

이 순서를 보면 딱 떠오르는 순회방식이 있다. 바로 중위 순회(Inorder)다. 

중위 순회란 트리의 여러 순회 방식 중 하나로 leftChild - rootNode - rightChild 순으로 방문하는 방식이다. 

 

이제 우리가 할 일은, 주어진 입력대로 트리를 생성한 후, 중위순회를 하면서 각 노드에 열의 번호를 부여하는 것이다.

이 문제 해결에 매우 중요한 주의할 점이 있다.

 

1. 루트 노드는 1번 노드가 아니다. 즉 3번 노드가 루트일 수도 있고 랜덤이다.

2. 노드 입력 순서는 1 -> 2 -> 3 -> .. 순으로 주어지지 않는다. 단말 노드가 먼저 나오고 루트 노드가 나올 수도 있다. 

 

2번 때문에 다 푼 문제의 입력부를 다 고쳤다. ㅠㅠ 

아무튼 입력을 잘 받고 트리를 제대로 생성하면, 중위 순회만 하면 끝이다.

순회를 마치면 각 레벨별로 최소 열, 최대 열의 번호를 알 수 있다.

따라서 레벨별 최대 너비를 구해 출력하면 끝이다. 

 

다른 블로그의 풀이를 보니 직접 트리를 만들진 않고, 배열을 이용해 잘 풀었던데, 난 왠지 트리는 class를 이용해 제대로 만들고 싶어서 그렇게 풀다보니 풀이가 길어졌다. 다른 풀이를 참고해도 상관없다.

 

 

코드 원본 : https://github.com/chosh95/STUDY/blob/master/BaekJoon/2020/%ED%8A%B8%EB%A6%AC%EC%9D%98%20%EB%86%92%EC%9D%B4%EC%99%80%20%EB%84%88%EB%B9%84%20(2250%EB%B2%88).cpp

chosh95/STUDY

 

C++ 코드

#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
using namespace std;
int N;
int minLevel[10001]; // 해당 레벨에서 최소 열
int maxLevel[10001]; // 해당 레벨에서 최대 열
int cur = 1; // inorder할 때 열을 기록해줄 변수
int levelCnt; // 최대 레벨을 기록하는 변수

int leftChild[10001]; // i번 노드의 왼쪽 자식
int rightChild[10001]; // i번 노드의 오른쪽 자식
int parentNum[10001]; // i번 노드의 부모 노드

struct Node {
	int data; 
	int level;
	Node* leftNode;
	Node* rightNode;
	Node(int data, int level, int left, int right) { //생성자
		this->data = data;
		this->level = level;

		levelCnt = max(level, levelCnt);

		if (left == -1) this->leftNode = NULL;
		else this->leftNode = new Node(left, level + 1, -1 , -1);

		if (right == -1) this->rightNode = NULL;
		else this->rightNode = new Node(right, level + 1, -1, -1);
	}
};

class Tree {
	Node* root;

	public:
		Tree(int parent, int left, int right) { // 트리 생성자
			this->root = new Node(parent, 1, left, right);
		}

		void insert(int parent, int left, int right) { // insert의 helper 함수
			insert(root, parent, left, right);
		}

		void insert(Node* currentNode, int parent, int left, int right) { // 트리에 노드 삽입하는 함수
			if (currentNode == NULL) return;
			if (currentNode->data == parent) { // 삽입할 노드를 찾았으면 left, right 생성
				if (left == -1) currentNode->leftNode = NULL;
				else currentNode->leftNode = new Node(left, currentNode->level + 1, -1, -1);
				if (right == -1) currentNode->rightNode = NULL;
				else currentNode->rightNode = new Node(right, currentNode->level + 1, -1, -1);
			}
			else { // 삽입할 곳을 찾아 재귀 호출
				insert(currentNode->leftNode, parent, left, right);
				insert(currentNode->rightNode, parent, left, right);
			}
		}

		void inorder() { //inorder의 helper 함수
			inorder(root);
		}

		void inorder(Node* currentNode) { // 중위순회
			if (currentNode == NULL) return;

			inorder(currentNode->leftNode); // left 방문

			minLevel[currentNode->level] = min(minLevel[currentNode->level], cur); // 현재 방문
			maxLevel[currentNode->level] = max(maxLevel[currentNode->level], cur); // 현재 레벨의 최소, 최대 열을 기록한다.
			cur++; // 열 증가

			inorder(currentNode->rightNode); // right 방문
		}
};

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	cin >> N;
	for (int i = 1; i <= N; i++) {
		minLevel[i] = 987654321; // min배열 최대값으로 초기화
		maxLevel[i] = 0;
	}

	for (int a, b, c, i = 1; i <= N; i++) {
		cin >> a >> b >> c;
		leftChild[a] = b; //a의 left, rightChild 기록
		rightChild[a] = c;
		if (b != -1) parentNum[b] = a; // b, c가 NULL이 아니면 a가 부모노드
		if (c != -1) parentNum[c] = a;
	}
	
	int rootNum = 0; // root 노드가 몇번인지 검색
	for (int i = 1; i <= N; i++) {
		if (parentNum[i] == 0) {
			rootNum = i;
			break;
		}
	}

	queue<int> q; // 트리에 삽입할 노드를 차례대로 저장하는 큐
	Tree t(rootNum, leftChild[rootNum], rightChild[rootNum]); //루트 노드를 이용해 트리 생성
	if (leftChild[rootNum] != -1) q.push(leftChild[rootNum]); // left, right가 NULL이 아니면 삽입
	if (rightChild[rootNum] != -1) q.push(rightChild[rootNum]);

	while (!q.empty()) {
		int cur = q.front();
		q.pop();
		t.insert(cur, leftChild[cur], rightChild[cur]); // left, right를 cur에 삽입
		if (leftChild[cur] != -1) q.push(leftChild[cur]); // 다음에 삽입할 노드 삽입
		if (rightChild[cur] != -1) q.push(rightChild[cur]);
	}

	t.inorder(); // 중위 순회

	int resLevel = 1, resWidth = 1; // 결과 레벨, 너비
	for (int i = 1; i <= levelCnt; i++) {
		if (resWidth < maxLevel[i] - minLevel[i] + 1) {
			resWidth = maxLevel[i] - minLevel[i] + 1;
			resLevel = i;
		}
	}

	cout << resLevel << " " << resWidth;
}