[JS] 백준 2178번 : 미로탐색 - 그래프이론

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

2178번: 미로 탐색

 

풀이방법

1. BFS로 풀어낸다.

2. 미로탐색을뻗어나가면서 레벨(L)도  같이 queue에 저장해준다.

3. 지정된 도착지점에 도착시 저장해주었던 L값에 +1을 한후 출력한다.

 

 

 

 

🤟내 제출

const fs = require("fs");
const filePath = process.platform === "linux" ? "/dev/stdin" : "./input.txt";
let input = fs.readFileSync(filePath).toString().trim();
input=input.replace(/\r/g,"").split("\n");

let [N,M]=input.shift().split(" ").map(Number);
let arr=[];
for(var i=0;i<N;i++){
    arr.push(input.shift().split("").map(Number));

}

let dx=[1,0,0,-1];
let dy=[0,-1,1,0];

let visited=Array.from({length:N},()=>Array(M).fill(0));
let queue=[];
visited[0][0]=1;
queue.push([0,0,0]);
let answer=0;
while(queue.length){
    let [y,x,L]=queue.shift();
    if(y==N-1 && x==M-1){
        answer=L+1;
        break;
    }
    for(var i=0;i<4;i++){
        let nx=x+dx[i];
        let ny=y+dy[i];
        if(nx>=0 && ny>=0 && ny<N && nx<M && arr[ny][nx]==1){
            if(visited[ny][nx]==0){
                visited[ny][nx]=1;
                queue.push([ny,nx,L+1]);
            }
        }
    }
}
console.log(answer)

 

 

💢어려웠던 점

1. 몇 칸을 지났는지의 값을 출력할 때 처음에 L 값을 큐에 저장하는 반복문이 끝나고 L++을 해줬는데 오답이 계속나왔다.

 - 문제가 무엇인지 몰랐지만 위와 같이 애초에 queue에 다음 칸을 넣을 때 레벨 값을 증가시켜서 출력했다.