[Javascript][BOJ] 1504 특정한 최단 경로

www.acmicpc.net/problem/1504

1504번: 특정한 최단 경로

 

핵심 아이디어

1=>N으로 이동하는데, 2개의 정점을 무조건 지나는 가장 최소의 경로의 가중치를 구하는 문제이다.

처음엔 어떻게 접근해야 할지 감을 잡지못하고, 모든 경로를 탐색하여 v1,v2을 포함하는 경로를 찾아내는 방법 밖에 구상하지 못했다.

풀이를 보니,

정답은

1->...->v1->...->v2->...->N

1->...->v2->...->v1->...->N

둘 중 하나가 되므로,

1->v1일때 최소 비용 + v1->v2일때 최소 비용 + v2->N일때 최소 비용

vs

1->v2일때 최소 비용 + v2->v1일때 최소 비용 + v1->N일때 최소 비용

을 비교하기만 하면되는 것이었다.

심지어 방문했던 공간을 재 방문하는 것도 되므로 각각 3번의 다익스트라 알고리즘을 적용할때 visited 처리를 해줄 필요도 없었다.

문제를 분할해서 생각하는 훈련을 지속적으로 해나가야겠다.

 

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 findShortestCost = (N, E, edges, start, target) => {
	const distance = Array.from({ length: N + 1 }, () => Infinity);

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

	while (!pq.isEmpty()) {
		const qe = pq.dequeue();
		const currentVertex = qe.element;

		for (const edge of edges[currentVertex]) {
			const [nextVertex, nextCost] = edge;

			if (distance[nextVertex] >= distance[currentVertex] + nextCost) {
				distance[nextVertex] = distance[currentVertex] + nextCost;
				pq.enqueue(nextVertex, distance[nextVertex]);
			}
		}
	}
	// console.log(distance);
	return distance[target];
};

const solution = function (N, E, edges, v1, v2) {
	const ans = Math.min(
		findShortestCost(N, E, edges, 1, v1) +
			findShortestCost(N, E, edges, v1, v2) +
			findShortestCost(N, E, edges, v2, N),

		findShortestCost(N, E, edges, 1, v2) +
			findShortestCost(N, E, edges, v2, v1) +
			findShortestCost(N, E, edges, v1, N)
	);

	console.log(ans !== Infinity ? ans : -1);
};

const input = [];
rl.on('line', function (line) {
	input.push(line);
}).on('close', function () {
	const [N, E] = input
		.shift()
		.split(' ')
		.map((e) => parseInt(e));
	const [v1, v2] = input
		.pop()
		.split(' ')
		.map((e) => parseInt(e));
	const edges = Array.from({ length: N + 1 }, () => []);

	for (const row of input) {
		const [start, dest, cost] = row.split(' ').map((e) => parseInt(e));
		edges[start].push([dest, cost]);
		edges[dest].push([start, cost]);
	}
	solution(N, E, edges, v1, v2);
	process.exit();
});