트리의 높이와 너비

문제

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

언어

JavaScript

순서도

트리 생성 및 루트 노드를 찾기 위한 parents 배열 생성
루트 노드 찾기
중위 순회를 하며, 트리를 배열 형태로 변환 (레벨은 1 부터 시작)
배열 형태의 트리에서 모든 노드를 각 레벨별로 모으기
각 레벨별로 너비 구하고, 최댓값 구하기 (레벨은 1 부터 시작)

문제 풀이 step 1

주어진 입력에 따라서 트리를 생성하고, 루트 노드를 찾습니다.
- 트리를 생성할 때는 Node 클래스 (왼쪽 서브트리 링크, 오른쪽 서브트리 링크) 를 생성해서 구현합니다.
- 그리고 각 노드들의 번호는 1 ~ N 까지라고 문제에 명시되어 있기 때문에, 각 노드는 배열의 원소로 저장할 수 있습니다.
  - [<1 empty item>, Node { left: 2, right: 3 }, Node { left: 4, right: 5 }, ..., Node { left: -1, right: -1 }]
- 루트 노드란 유일하게 부모 노드가 없는 노드입니다. 따라서 각 노드들의 부모 노드를 기록한 후, 부모 노드가 없는 노드를 찾습니다.
  - 루트 노드를 찾는 이유는 뭘까요??
  - 트리의 순회를 하기 위해서는 루트 노드가 무엇인지 알아야 해서 그렇습니다.

문제 풀이 step 2

각 레벨의 너비를 구하려면, 각 노드가 몇 번째 레벨 (level) 이며, 몇 번째 열 (col) 에 있는지 알아야합니다.
- 이는 트리의 순회 중에서 중위 순회 (In-Order) 를 이용해서 구현할 수 있습니다.
- 중위 순회를 진행하면 왼쪽 -> 가운데 -> 오른쪽 순서를 보장하며 탐색을 할 수 있습니다.
- 그래서 맨 왼쪽부터 노드를 차례대로 탐색하며, 그 노드의 레벨과 열 번호를 배열에 기록합니다.
- 이때, 열 번호는 별도로 기록할 필요 없이 요소의 index 가 곧 열 번호가 됩니다.
- 이 과정을 진행하면 [<1 empty item>, 4, 3, 2, 5, 4, ..., 4, 3] 과 같은 배열을 얻을 수 있습니다.

문제 풀이 step 3

각 레벨의 노드들의 열 번호를 알게 되었으니, 이제 각 레벨끼리 노드들을 모으고, 너비를 구하면 됩니다.
- 생성한 배열을 순회하며, 각 레벨 별로 노드의 열 번호를 모아주면 됩니다. (열 번호는 곧 index 입니다.)
- 모았으면, 각 레벨 별로 너비를 구하면 됩니다.
구한 너비 중에서 최댓값이 정답이 됩니다.

후기

꼭 다시 풀어볼 문제입니다.
문제에서 “노드들의 번호가 1 부터 N 까지” 라고 명시되어 있어서 트리를 구현하는 것이 간편했던 것 같습니다.
현재 제 풀이는 중위 순회를 통해서 각 노드의 열 번호를 기록하고, 이후에 각 레벨 별로 모으는 순서로 로직이 진행됩니다.
- 이 두 과정을 합칠 수 도 있을 것 같습니다.
- 중위 순회를 하며, 배열에 넣을 때마다 어떤 값을 1 씩 증가시키면서 하면 될 것 같습니다.
좀 더 쉬운 풀이로 쉽게 설명하고 싶었지만, 아직 내공이 부족한 듯 합니다. (다음에는 꼭…!!)

소스 코드

const input = require("fs")
	.readFileSync("/dev/stdin")
	.toString()
	.trim()
	.split("\n");

class Node {
	constructor(left, right) {
		this.left = left;
		this.right = right;
	}
}

const inOrder = (treeArr, nodes, index, depth) => {
	if (index < 0) return;

	inOrder(treeArr, nodes, nodes[index].left, depth + 1);
	treeArr.push(depth);
	inOrder(treeArr, nodes, nodes[index].right, depth + 1);
};

const solution = (input) => {
	const n = parseInt(input[0]);

	const nodes = [];
	const parents = [];

	// 1. 트리 생성 및 루트 노드를 찾기 위한 parents 배열 생성
	for (let i = 1; i < n + 1; i++) {
		const [root, left, right] = input[i].split(" ").map(Number);
		nodes[root] = new Node(left, right);

		parents[left] = root;
		parents[right] = root;
	}

	// 2. 루트 노드 찾기
	let root = null;
	for (let i = 1; i < n + 1; i++) {
		if (parents[i] === undefined) root = i;
	}

	// 3. 중위 순회를 하며, 트리를 배열 형태로 변환 (레벨은 1 부터 시작)
	const treeArr = [];
	inOrder(treeArr, nodes, root, 1);

	// 4. 배열 형태의 트리에서 모든 노드를 각 레벨별로 모으기
	const widths = [];
	for (let i = 0; i < n; i++) {
		const level = treeArr[i];

		if (widths[level] === undefined) widths[level] = [];
		widths[level].push(i);
	}

	let level = null;
	let max = 0;
	// 5. 각 레벨별로 너비 구하고, 최댓값 구하기 (레벨은 1 부터 시작)
	for (let i = 1; i < widths.length; i++) {
		const width = widths[i][widths[i].length - 1] - widths[i][0] + 1;

		if (max < width) {
			level = i;
			max = width;
		}
	}

	return `${level} ${max}`;
};

console.log(solution(input));