[JavaScript] 백준 2178 : 미로 탐색

class : 3
level : silver 1
문제 링크 : 미로 탐색

2178번: 미로 탐색

My Solution

let fs = require('fs');
let input = fs.readFileSync('/dev/stdin').toString().trim();
input = input.split('\n');
const [N,M] = input.shift().split(' ').map(Number);
input = input.map(str=>str.split('').map(Number));
let matrix = input.map(arr=>arr.map(v=>v===1?true:false));
matrix[0][0] = false;
let queue = [[0,0,1]]
while(queue.length > 0){
    const [x,y,count] = queue.shift();
    if(x===M-1&&y===N-1){
        console.log(count);
        break;
    }
    if(x>0){
        if(matrix[y][x-1]){
            queue.push([x-1,y,count+1]);
            matrix[y][x-1] = false;
        }
    }
    if(x<M-1){
        if(matrix[y][x+1]){
            queue.push([x+1,y,count+1]);
            matrix[y][x+1] = false;
        }
    }
    if(y>0){
        if(matrix[y-1][x]){
            queue.push([x,y-1,count+1]);
            matrix[y-1][x] = false;
        }
    }
    if(y<N-1){
        if(matrix[y+1][x]){
            queue.push([x,y+1,count+1]);
            matrix[y+1][x] = false;
        }
    }
}

풀이방법
input을 N x M Array로 변형하였고 방문을 확인하기 위하여 N x M Array 형태의 matrix를 만들고 이동 가능한 칸에는 true를 이동불가한 칸은 false로 설정을 해 놓았다.
이 문제는 DFS로 풀수도 있지만 모든 방법을 구한 다음 가장 작은 값을 찾아야 하니 완전 탐색을 해야하는 형태로 변질된다.
따라서 BFS를 이용하여 풀었다.
queue에 [x,y,count]형태로 집어 넣는다.
처음 (x,y)기준 (0,0)에서 count를 1로 시작한다.(queue에 미리 집어 넣는다.)
queue의 크기가 0이상일 경우 while문을 이용하여 아래의 작업을 반복한다.
queue를 dequeue하여 한 개의 array를 추출한다. 추출한 array에서 x, y, count값을 추출한다.
x와 y의 값이 각각 M-1, N-1일 경우 count를 출력하고 while문을 빠져나온다.
x와 y의 값에 의하여 상하좌우를 탐색하여 방문하지 않은 좌표와 count+1을 queue에 넣는다.
방문하지 않은 좌표와 동일한 matrix의 좌표에 있는 값을 false로 바꾼다.


느낀점
그래프 문제를 이용한 DFS, BFS문제가 매우 많은 것 같다.
익숙한 것 같으면서 약간씩 다르니 좀더 적응을 해야할 것 같다.