[백준] 1261번 알고스팟_Node.js

 

문제

https://www.acmicpc.net/problem/1261

1261번: 알고스팟

---

문제 풀이

 해당 문제는 BFS문제이다. 하지만 도달하는 최단 거리가 아닌 벽을 최소한으로 부수는 경우를 찾는 것이다. 그렇기에 탐색에 있어서 우선순위가 존재한다.

 

벽을 최대한 부수지 않는 방식으로 진행하되 목적지에 도달 할 수 없을 때 최소의 벽을 부순다. 이를 구현하기 위해서는 BFS에서 사용되는 queue에 우선순위 별로 넣으면 된다.

 

기존의 문제에서 queue를 사용할 때는 새로운 케이스를 push한다. 이후 shift를 통해 가장 왼쪽(가장 최초로 들어온 데이터)를 꺼내어 사용한다.

하지만 우선순위를 높이기 위해 unshift를 진행하여 우선순위가 가장 높게 설정하여 벽을 최소한으로 부수도록 작동하게 하는 것이다.

 

풀이 코드

const fs = require('fs');
const stdin = (process.platform === 'linux'? fs.readFileSync('/dev/stdin').toString() :
`4 2
0001
1000`).split('\n');

const input = (() => {
    let line = 0;
    return () => stdin[line++];
})();

const [tx,ty] = input().split(' ').map(Number);
let visited = Array.from({length : ty},()=>Array(tx).fill(0));
let maze = Array.from({length:ty},()=>input().split('').map(Number));

const queue = [[0,0,0]];
visited[0][0] = 1;

const move = {
    up(x,y){
        return [x,y-1];
    },
    down(x,y){
        return [x,y+1];
    },
    right(x,y){
        return [x+1,y];
    },
    left(x,y){
        return [x-1,y];
    }
}

while(queue.length){
    const [x,y,time] = queue.shift();
    // console.log(x,y,time);
    if(x === tx-1 && y === ty-1){
        // console.log('>>>',x,y,time);
        console.log(time);
        break;
    }

    for( action of ['up','down','right','left']){
        const [nx,ny] = move[action](x,y);
        if(ny < 0 || ny >= ty || nx < 0 || nx >= tx) continue;
        if(visited[ny][nx]) continue;
        if(maze[ny][nx]){
            queue.push([nx,ny,time+1]);
            visited[ny][nx] = 1;
        }else{
            queue.unshift([nx,ny,time]);
            visited[ny][nx] = 1;
        }
    }
}