트리의 지름

문제

언어

  • JavaScript

순서도

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

문제 풀이 step 1

문제 풀이 step 2

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

문제 풀이 step 3

  • 단, 이번 문제에서는 예외처리가 하나 필요합니다.
  • 주어지는 노드의 개수의 범위가 1 ~ 10000 입니다.
  • 따라서 노드가 1 인 경우에 대한 예외처리를 해줘야 합니다.
  • 트리의 지름은 두 노드 사이의 경로의 길이이므로, 노드가 한 개라면 트리의 지름은 0 입니다.

소스 코드

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 [remoteVertex, remoteDistance];
};

const solution = (input) => {
	const n = parseInt(input[0]);
	// 노드가 한 개인 경우 예외 처리
	if (n === 1) return 0;

	// 주어진 입력에 따라서 인접리스트 생성
	const graph = Array.from({length: n + 1}, () => []);
	for (let i = 1; i < n; i++) {
		const [from, to, weight] = input[i].split(" ").map(Number);

		graph[from].push([to, weight]);
		graph[to].push([from, weight]);
	}

	let [remoteVertex, remoteDistance] = BFS(n, graph, 1);
	[remoteVertex, remoteDistance] = BFS(n, graph, remoteVertex);

	return remoteDistance;
};

console.log(solution(input));