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]);
})'알고리즘-문제' 카테고리의 다른 글
| 백준 1700 멀티탭 스케줄링 node.js (0) | 2024.03.12 |
|---|---|
| 백준 17298 오큰수 자바스크립트 (0) | 2024.03.04 |
| 백준 9934 완전 이진트리 node.js (0) | 2024.02.25 |
| 프로그래머스 여행경로 자바스크립트 (0) | 2024.02.20 |
| 구름톤 챌린지 3주 차 문제 14 학습 일기 (0) | 2024.02.18 |
