[BFS] 백준 2206 벽부수고 이동하기

문제 :

벽을 1번까지는 부수고 지나갈 수 있다는 조건이 추가되었을 때, BFS 알고리즘으로 미로에서 최단거리 찾기

 

 

 

해결방법 :

기존 BFS로 최단거리 찾는 알고리즘 + visited 배열을 (벽을 한 번도 안 뚫은 경우 - 1개까지 뚫은 경우 - .... - N개까지 뚫은 경우) 벽 부순 개수에 따라 나눈 3차원 배열로 만들어서 해결한다.

 

 

큐에서 꺼낸 지점의 상하좌우를 탐색할 때..

1) 벽일 경우

아직 벽을 안 부수었으면 이 벽을 부수고 이동하는 케이스도 큐에 넣는다.

(3차원 배열상에서 아래로 떨어지는 것처럼 이동)

 

2) 길일 경우

자기 층 내에서 일반 BFS 미로 찾기처럼 진행. 

 

 

 

 

 

node.js 코드

const readline = require('readline');
const rl = readline.createInterface(process.stdin, process.stdout);

let input = [];
let n,m;

function Queue(){
  var a=[],b=0;
  this.getLength=function(){return a.length-b};
  this.isEmpty=function(){return 0==a.length};
  this.enqueue=function(b){a.push(b)};
  this.dequeue=function(){if(0!=a.length){
      var c=a[b];
      2*++b>=a.length&&(a=a.slice(b),b=0);
      return c}};
  this.peek=function(){return 0<a.length?a[b]:void 0}
};

let bfs = (maze) => {
  let dx = [-1,1,0,0], dy=[0,0,-1,1];
  let visited = Array.from(Array(n), () => Array.from(Array(m), ()=>[0,0]));
  let q = new Queue();
  
  visited[0][0]=[1,0];
  q.enqueue([0,0,0]);
  let result = -1;

  while(!q.isEmpty()){
    let [x,y,w] = q.dequeue();
    //reached destination
    if(x==n-1 && y==m-1) {
      result = visited[x][y][w];
      break;
    }
    for(var i=0; i<4; i++){
      let nx = x + dx[i], ny = y+dy[i];
      if( nx<0 || nx>=n || ny<0 || ny>=m) continue;
      if(maze[nx][ny]==1){
        if(w==1) continue;
        visited[nx][ny][1] = visited[x][y][w]+1; 
        q.enqueue([nx,ny,1]);
      }else{
        if(visited[nx][ny][w]!=0) continue;
        visited[nx][ny][w] = visited[x][y][w]+1;
        q.enqueue([nx,ny,w]);
      }


    }
  }
  
  return result;
}


let eval = () => {
 [n,m] = input[0].split(' ').map((el)=>+el);
 let maze = input.slice(1).map((x)=>x.split(''));
 console.log(bfs(maze));
}

rl.on('line', function(line){
  input.push(line);
}).on('close', eval);

 

 

 

문제 링크 : https://www.acmicpc.net/problem/2206