[Javascript][BOJ] 11403 경로 찾기 (플로이드 와샬)

www.acmicpc.net/problem/11403

11403번: 경로 찾기

 

핵심 아이디어

해당 위치에서의 경로가 존재하는지 판단하는 문제로, 플로이드 와샬 알고리즘으로 해결할 수 있다.

플로이드 와샬 알고리즘은 dp 개녕을 깔고 들어가는데,

모든 정점to정점을 순회하되, 중간지점인 k를 두어서, k를 거쳐하는 경로가 더 짧은 경우에 matrix값을 갱신시켜주는 역할을 한다.

 

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

const solution = function (input) {
	const n = parseInt(input.shift());
	const edgeMatrix = [];
	const resultMatrix = Array.from({ length: n }, () =>
		Array.from({ length: n }, () => Infinity)
	);
	for (const row of input) {
		edgeMatrix.push(row.split(' ').map((e) => parseInt(e)));
	}

	for (let i = 0; i < n; i++) {
		for (let j = 0; j < n; j++) {
			if (edgeMatrix[i][j] === 0) continue;
			resultMatrix[i][j] = edgeMatrix[i][j];
		}
	}

	for (let k = 0; k < n; k++) {
		for (let i = 0; i < n; i++) {
			for (let j = 0; j < n; j++) {
				if (resultMatrix[i][j] > resultMatrix[i][k] + resultMatrix[k][j]) {
					resultMatrix[i][j] = resultMatrix[i][k] + resultMatrix[k][j];
				}
			}
		}
	}
	let ans = '';
	for (const row of resultMatrix) {
		ans += `${row
			.map((e) => {
				return e === Infinity ? 0 : 1;
			})
			.join(' ')}\n`;
	}
	console.log(ans.trim('\n'));
};

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