트리의 지름

문제

언어

  • JavaScript

순서도

  1. 그래프 생성
  2. 2 번의 BFS 탐색

문제 풀이 step 1

  • 트리의 지름이란, 트리에서 임의의 두 점 사이의 거리 중 가장 긴 것을 말한다고 합니다.
  • 트리의 지름을 구해야 하는데, 다음과 같은 방법으로 트리의 지름을 구할 수 있다고 합니다.
  • 임의의 정점에서 BFS 탐색을 통해 가장 먼 정점을 구하고, 그 정점에서 BFS 탐색을 한 번 더 해서 가장 먼 정점을 구했을 때, 두 정점 사이의 거리가 트리의 지름이라고 합니다.
  • 저는 원리를 정확하게 이해하진 못해서 우선은 외우는 방식을 선택했습니다.

문제 풀이 step 2

  • 우선 주어진 입력으로 인접리스트 형식의 그래프를 생성합니다.
    • 트리도 그래프이기 때문에 그래프 표현 방식을 사용할 수 있습니다.
    • 이번에는 단순 그래프가 아니라 가중치 그래프이기 때문에 정점을 저장할 때 가중치도 같이 저장합니다.
    • [vertex, weight] 이런 양식으로 저장합니다.
  • 생성한 그래프를 시작 정점을 1 번 정점으로 해서 BFS 탐색을 실시합니다.
    • 1 번 정점은 항상 존재하니까 시작 노드로 선택했습니다.
    • 매 탐색마다 시작 정점으로부터의 거리를 기록하면서 탐색합니다.
    • 동시에, 시작 정점으로부터 가장 먼 거리의 정점이 어떤 정점인지 갱신합니다.
    • 저는 거리를 기록하는 것으로 방문 처리를 대신했습니다.
  • 한 번의 BFS 탐색을 실시하면, 시작점으로부터 가장 먼 정점이 어떤 정점인지 알게됩니다.
    • 이제 그 가장 먼 정점을 시작점으로 잡아서 한 번 더 BFS 탐색을 실시합니다.
  • 두 번째의 BFS 탐색을 통해서 얻은 가장 먼 거리가 정답이 됩니다.
  • 자세한 설명은 주석에 추가하겠습니다.

소스 코드

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

class Queue {
	constructor() {
		this.bucket = [];
		this.front = -1;
		this.rear = -1;
	}

	isEmpty() {
		return this.front === this.rear;
	}

	enqueue(data) {
		this.bucket[++this.rear] = data;
	}

	dequeue() {
		if (this.isEmpty()) return;
		return this.bucket[++this.front];
	}
}

const BFS = (n, graph, start) => {
	const distance = Array(n + 1).fill(-1);
	const queue = new Queue();

	let remoteVertex = null;
	let remoteDistance = 0;

	queue.enqueue(start);
	distance[start] = 0;

	while (!queue.isEmpty()) {
		const from = queue.dequeue();

		for (let i = 0; i < graph[from].length; i++) {
			const [to, weight] = graph[from][i];

			if (distance[to] !== -1) continue;

			queue.enqueue(to);
			// 매 탐색 시 시작점으로부터의 거리를 갱신 (이를 통해서 방문 처리를 대신)
			distance[to] = distance[from] + weight;

			// 시작점으로부터 가장 먼 정점과 그 거리를 갱신
			if (distance[to] > remoteDistance) {
				remoteVertex = to;
				remoteDistance = distance[to];
			}
		}
	}

	// 가장 먼 정점과 그 거리를 return
	return [remoteVertex, remoteDistance];
};

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

	// 인접리스트 형식의 그래프 생성
	const graph = Array.from({length: n + 1}, () => []);
	for (let i = 1; i < n + 1; i++) {
		const line = input[i].split(" ").map(Number);
		const from = line[0];

		for (let j = 1; line[j] !== -1; j += 2) {
			const [to, weight] = [line[j], line[j + 1]];

			// 정점과 가중치를 같이 저장
			graph[from].push([to, weight]);
		}
	}

	// 1 번 정점을 시작으로 BFS 탐색을 통해서 가장 먼 정점을 구합니다.
	let [remoteVertex, remoteDistance] = BFS(n, graph, 1);

	// 첫 번째 BFS 탐색을 통해서 얻은 정점을 시작으로 BFS 탐색을 통해서 가장 먼 거리를 구합니다.
	[remoteVertex, remoteDistance] = BFS(n, graph, remoteVertex);

	return remoteDistance;
};

console.log(solution(input));