[Javascript][BOJ] 1967 트리의 지름

www.acmicpc.net/problem/1967

1967번: 트리의 지름

 

핵심 아이디어

트리의 지름을 구하는 문제는 풀이법이 정해져있는것 같다.

핵심은 무작위의 점에서 가장 멀리 있는 점을 구한뒤, 그 점에서 한번 더 가장 멀리있는 점과의 거리가 트리의 지름이 된다는 것이다.

즉, 1번 노드에서 다익스트라를 이용해 가장 멀리 있는 노드 x를 구하고,

x에서 한번 더 다익스트라 알고리즘을 통해 가장 멀리 있는 노드사이의 거리를 구하면된다.

 

const readline = require('readline');
const rl = readline.createInterface({
	input: process.stdin,
	output: process.stdout,
});

class QElement {
	constructor(element, priority) {
		this.element = element;
		this.priority = priority;
	}
}

class PriorityQueue {
	constructor() {
		this.queue = [];
	}
	enqueue(element, priority) {
		let isContain = false;
		const qElement = new QElement(element, priority);
		for (let i = 0; i < this.queue.length; i++) {
			if (this.queue[i].priority > qElement.priority) {
				this.queue.splice(i, 0, qElement);
				isContain = true;
				break;
			}
		}
		if (!isContain) {
			this.queue.push(qElement);
		}
	}
	dequeue() {
		if (!this.isEmpty()) return this.queue.shift();
	}
	front() {
		if (!this.isEmpty()) return this.queue[0];
	}
	rear() {
		if (!this.isEmpty()) return this.queue[this.queue.length - 1];
	}
	isEmpty() {
		return this.queue.length === 0;
	}
}

const dijkstra = (n, start, edges) => {
	const distance = Array.from({ length: n + 1 }, () => Infinity);
	const pq = new PriorityQueue();
	let maxCost = 0;
	let farestNode = start;

	distance[start] = 0;
	pq.enqueue(start, 0);

	while (!pq.isEmpty()) {
		const currPos = pq.dequeue().element;
		for (const [dest, cost] of edges[currPos]) {
			if (distance[dest] >= distance[currPos] + cost) {
				distance[dest] = distance[currPos] + cost;
				if (maxCost <= distance[dest]) {
					maxCost = distance[dest];
					farestNode = dest;
				}
				pq.enqueue(dest, distance[dest]);
			}
		}
	}

	return [maxCost, farestNode];
};

const solution = function (input) {
	const n = parseInt(input.shift());
	const edges = Array.from({ length: n + 1 }, () => []);
	for (const row of input) {
		const [a, b, c] = row.split(' ').map((e) => parseInt(e));
		edges[a].push([b, c]);
		edges[b].push([a, c]);
	}

	const farestNode = dijkstra(n, 1, edges)[1];
	console.log(dijkstra(n, farestNode, edges)[0]);
};

const input = [];
rl.on('line', function (line) {
	input.push(line);
}).on('close', function () {
	solution(input);
	process.exit();
});