[Javascript][BOJ] 1956 운동 (플로이드 와샬, 사이클)

www.acmicpc.net/problem/1956

1956번: 운동

 

핵심 아이디어

가장 작은 사이클을 가지는 경로의 전체 가중치를 구하는 문제이다.

여기서 사이클을 판단하는 방법으로는 union find를 생각했었는데,

그 보다 더 간단한 방법이 있었다.

바로 '플로이드 와샬'방법을 사용하는 것!

일반적으로 플로이드 와샬 알고리즘을 사용할때에는 i->i인 경로, 즉 matrix[i][i]는 INF으로 통일한다.

하지만 i->i경로 matrix[i][i]가 INF보다 작은 값을 가진다면?

바로 사이클이 돌고있는것이다!

결국엔 플로이드 와샬 알고리즘을 사용해주고 matrix[i][i] 값들 중 가장 작은 값을 출력해주면된다.

* 답이 INF이면 -1를 출력해주는 것을 꼭 기억하자! (문제 잘 읽기)

 

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

const solution = function (input) {
	const [V, E] = input
		.shift()
		.split(' ')
		.map((e) => parseInt(e));
	const matrix = Array.from({ length: V + 1 }, () =>
		Array.from({ length: V + 1 }, () => Infinity)
	);

	for (const row of input) {
		const [a, b, c] = row.split(' ').map((e) => parseInt(e));
		matrix[a][b] = Math.min(matrix[a][b], c);
	}

	for (let k = 0; k < V + 1; k++) {
		for (let i = 0; i < V + 1; i++) {
			if (k === i) continue;
			for (let j = 0; j < V + 1; j++) {
				if (k === j) continue;
				if (matrix[i][j] > matrix[i][k] + matrix[k][j]) {
					matrix[i][j] = matrix[i][k] + matrix[k][j];
				}
			}
		}
	}

	let min = Infinity;
	for (let i = 0; i < V + 1; i++) {
		min = Math.min(min, matrix[i][i]);
	}
	console.log(min !== Infinity ? min : -1);
};

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