[백준][Node.js] 2178번 : 미로 탐색

 

 

Algorithm

-  미로 탐색 -

 

---

 

문제

N×M크기의 배열로 표현되는 미로가 있다.

1	0	1	1	1	1
1	0	1	0	1	0
1	0	1	0	1	1
1	1	1	0	1	1

미로에서 1은 이동할 수 있는 칸을 나타내고, 0은 이동할 수 없는 칸을 나타낸다. 이러한 미로가 주어졌을 때, (1, 1)에서 출발하여 (N, M)의 위치로 이동할 때 지나야 하는 최소의 칸 수를 구하는 프로그램을 작성하시오. 한 칸에서 다른 칸으로 이동할 때, 서로 인접한 칸으로만 이동할 수 있다.

위의 예에서는 15칸을 지나야 (N, M)의 위치로 이동할 수 있다. 칸을 셀 때에는 시작 위치와 도착 위치도 포함한다.

 

입출력 예시

 

문제 풀기

let BFS = function (q, v, r) {
	while (q.length !== 0) {
		let shiftQ = q.shift();
		let [x, y] = [shiftQ[0], shiftQ[1]];
		for (let i = 0; i < 4; i++) {
			let nx = x + dx[i];
			let ny = y + dy[i];
			// 방문한적이 없고 0이 아니라면
			if (0 <= nx && nx < r[0] && 0 <= ny && ny < r[1]) {
				if (v[nx][ny] === false && input[nx][ny] !== 0) {
					q.push([nx, ny]);
					input[nx][ny] = input[x][y] + 1;
					v[nx][ny] = true;
				}
			}
		}
	}
	return;
};

const readline = require("readline");
const rl = readline.createInterface({
	input: process.stdin,
	output: process.stdout,
});
let input = [];
let queue = [];
let dx = [0, 0, -1, 1]; // x기준 상하좌우
let dy = [-1, 1, 0, 0]; // y기준 상하좌우
rl.on("line", function (line) {
	input.push(line.toString());
}).on("close", function () {
	let range = input
		.shift()
		.split(" ")
		.map((el) => Number(el));
	input = input.map((el) => el.split("").map((el) => Number(el)));
	let visited = Array.from(Array(range[0]), () => Array(range[1]).fill(false));
	visited[0][0] = true;
	queue.push([0, 0]);
	BFS(queue, visited, range);
	console.log(input[range[0] - 1][range[1] - 1]);
	process.exit();
});