[Javascript][BOJ] 2665 미로만들기

www.acmicpc.net/problem/2665

2665번: 미로만들기

 

핵심아이디어

bfs와 dp를 적절히 섞어쓰면 되는 문제이다.

예전에 python으로 풀었는데 지금 풀어보려하니 아이디어가 잘 떠오르지 않았다.

dp[x][y] 를 x,y좌표까지 도달할때 소모해야 하는 최소 검은방의 개수로 정의하고 bfs를 돌리면된다.

그리고 이때에는 visited를 사용하면 안되는데 그 이유는, 각 방의 최소값을 계속 판단하여 dp값을 업데이트해주어야 하는데,

visited으로 초반에 방문처리를 해버리면 값이 고정되어 버리기 때문이다.

 

 

 

'use strict';

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

const solution = function (input) {
	const n = parseInt(input.shift());
	const board = [];
	const dp = []; // dp[x][y], x,y 최소로 검은방을 지나서 도달할 수 있는 값
	// const visited = [];
	for (const row of input) {
		board.push(Array.from(row).map((e) => parseInt(e)));
		dp.push(Array.from({ length: n }, () => Infinity));
		// visited.push(Array.from({ length: n }, () => 0));
	}
	const direction = [
		[-1, 0],
		[1, 0],
		[0, -1],
		[0, 1],
	];
	// 시작지점 초기화
	const q = [[0, 0]];
	dp[0][0] = 0;

	while (q.length > 0) {
		const [x, y] = q.shift();
		// visited[x][y] = 1;
		for (const [a, b] of direction) {
			const [nx, ny] = [x + a, y + b];
			if (nx >= 0 && ny >= 0 && nx < n && ny < n) {
				// 유효성 체크
				// if (!visited[nx][ny]) {
				if (board[nx][ny] === 1) {
					// 흰방이면 이전방의 값 이하일때 그대로 가져옴
					if (dp[nx][ny] > dp[x][y]) {
						dp[nx][ny] = dp[x][y];
						q.push([nx, ny]);
					}
				} else {
					// 검은방일때에는 +1해서(검은방을 부수어서) 도달하는 것이 더 작은 경우에만 +1하여 이동
					if (dp[nx][ny] > dp[x][y] + 1) {
						dp[nx][ny] = dp[x][y] + 1;
						q.push([nx, ny]);
					}
				}
				// }
			}
		}
	}
	console.log(dp[n - 1][n - 1]);
	// console.log(dp.join('\n'));
};

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