[Javascript][BOJ] 1446 지름길

www.acmicpc.net/problem/1446

1446번: 지름길

 

핵심 아이디어

단방향의 경로가 주어진 다익스트라 문제이다.

예제를 풀이하자면

0부터 150까지 움직이는데, 가장 최소의 비용을 구하라는 문제로,

0 -> 50

50 -> 100

위 2가지의 지름길로 이동하고

100부터 150까지는 정상적으로 이동해서 총 비용이 70이된다.

 

이 문제와 다른 문제의 차이점은 지름길에 주어진, 값들만 노드로 존재하는 것이 아니라

0~D까지의 모든 지점에 대해 다익스트라를 수행해야 한다는 것이다.

즉 dp[i]를 i(km) 지점 까지 걸리는 가장 최소의 시간으로 정의하고 dp를 D+1 길이 만큼 선언해야 한다는 뜻이다.

또한, 이 문제에서 

"모든 지름길은 일방통행이고, 고속도로를 역주행할 수는 없다"

제한 조건이 있길래 이러한 예제는 없는 것으로 보고 별도의 처리를 해주진 않았는데,

역주행 지름길이 실제로 주어지는 것같다. (처리해주니까 바로 통과)

 

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 solution = function (input) {
	const [N, D] = input
		.shift()
		.split(' ')
		.map((e) => parseInt(e));
	//dp[i] ikm까지 이동시에 걸리는 최소 시간
	const dp = Array.from({ length: D + 1 }, () => Infinity);
	const edges = Array.from({ length: D + 1 }, () => []);
	for (const row of input) {
		const [a, b, c] = row.split(' ').map((e) => parseInt(e));
		if (D < b) continue;
		if (b - a <= c) continue;
		edges[a].push([b, c]);
	}
	const pq = new PriorityQueue();

	dp[0] = 0;
	for (let start = 0; start <= D; start++) {
		if (start > 0) {
			dp[start] = Math.min(dp[start], dp[start - 1] + 1);
		}

		pq.enqueue(start, dp[start]);
		while (!pq.isEmpty()) {
			const qe = pq.dequeue();
			const currPos = qe.element;

			for (const [nextPos, nextDist] of edges[currPos]) {
				if (dp[nextPos] > dp[currPos] + nextDist) {
					dp[nextPos] = dp[currPos] + nextDist;
					pq.enqueue(nextPos, dp[nextPos]);
				}
			}
		}
	}
	console.log(dp[D]);
};

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