백준 1261 알고스팟 node.js

2206번 벽 부수고 이동하기와 매우 유사한 0-1bfs, 데이크스트라 문제이다.

두가지 해결법이 있는데,

0-1bfs로 접근한다면

 

dist배열에는 2차원 배열에서 해당 좌표까지 도착했을 때 벽을 부순 횟수를 기록하고

벽을 부순 횟수가 더 적을 때 deque에 삽입한다

 

우리는 최대한 벽을 부수지 않으면서 멀리 갈 수 있어야 한다.

때문에 벽을 부수지 않고 전진하는 경우 deque의 front에 삽입하고

벽을 부수는 경우 deque의 back에 삽입한다.

 

하지만 이건 내가 데이크스트라를 통해 문제를 해결한 이후에 본 풀이법이다.

 

데이크스트라로 접근하는 것이 더 이해가 쉬울 수 있다.

기존 데이크스트라는 탐색 시점 최단 거리의 노드를 queue에 넣고, 

방문한 노드 기준으로 다시 연결된 노드의 최단거리를 갱신시켜 주는데

 

이 문제에서는 기준을 최단거리가 아닌 벽을 부순 횟수로 바꾸면 된다.

 

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

const input = [];
rl.on('line', (line)=>{
	input.push(line);
}).on('close', ()=>{

	const [m,n] = input[0].split(' ').map(Number);

	const map = Array.from(Array(n), () => Array(m).fill(0));

	for(let i = 0; i < n; i++){
		const arr = input[i+1].split('').map(Number);
		for(let j = 0; j < m; j++)
			map[i][j] = arr[j];
	}

	const dist = Array.from(Array(n), () => Array(m).fill(Infinity));
	const bfs = () => {
		const q = [];
		q.push([0,0,0]);

		while(q.length > 0){
			const [y_,x_,v] = q.shift();

			const a = [1,-1,0,0];
			const b = [0,0,-1,1];

			for(let i = 0; i < 4; i++){
				const y = y_ + a[i];
				const x = x_ + b[i];
				if(x >= 0 && x < m && y >= 0 && y < n){
					if(map[y][x] === 0 && dist[y][x] > v){
						dist[y][x] = v;
						q.push([y,x,v]);
					}
					else if (map[y][x] === 1 && dist[y][x] > v + 1){
						dist[y][x] = v + 1;
						q.push([y,x,v+1]);
					}
				}
			}
		}
	}

	bfs();
	if(dist[n-1][m-1] === Infinity)
		console.log(0)
	else
		console.log(dist[n-1][m-1]);

})