Shortest path in a Binary Maze

www.geeksforgeeks.org/shortest-path-in-a-binary-maze/?ref=lbp

- 문제 내용

M x N 사이즈의 Grid에서 [0,0]을 소스로 하고 [M-1,N-1]을 목적지로 한 1과 0으로만 만들어진 Maze에서 출력 가능한 모든 Path를 출력하라. (최소 패스도 가능)

- 접근 방법 : BFS Search

BFS Search를 위해서는 다음 고려사항을 생각해야 한다.

1. Queue를 만들 것
2. count 1회에 들어온 모든 Queue를 소비하고 count를 1 증가 시킬 것
3. Visited 된 Cell은 다시 Queue에 넣지 말것
4. End를 만나면 해당 Path는 종료 시킬 것
   -> 이 부분을 return count로 하게 되면 최소 Path count 값을 출력 할 수 있다.

            if (row == maze.length - 1 && col == maze[0].length - 1) {
                return count;
            }

 마지막으로 모든 Path를 trace 하는 것이다.

이 부분이 다소 까다로운데 두가지 접근이 가능할 것 같다.

1. queue 루프를 다 돌고 나서 destination 부터 이웃 cell의 count 숫자를 보고 1씩 줄여나가면서 path를 print한다.
2. queue 루프를 돌때 모든 경우의 path를 유지 시킨다.

아래 코드는 위의 2번을 구현한 코드다. 아무래도 1번 같은 경우 한번더 dfs를 해야한다는 부담이 있다.

 

function solution(maze) {
    let scoreArr = new Array(maze.length).fill(0).map(_=> new Array(maze[0].length).fill(0));

    let queue = new Array();
    queue.push([[0, 0]]);

    let count = 1;
    let resultPath = new Array();
    while(0 < queue.length){
        let length = queue.length;

        for (let i = 0; i < queue.length; i++) {
            let path = queue.shift();
            let [row, col] = path[path.length -1];

            if (row == maze.length - 1 && col == maze[0].length - 1) {
                resultPath.push(path);
                continue;
            }

            if (0 < scoreArr[row][col]) continue;

            scoreArr[row][col] = count;

            //north
            if (0 < row && maze[row - 1][col] == 0 && 0 == scoreArr[row - 1][col]) {
                path.push([row - 1, col]);
                queue.push(path);
            }
            //south
            if (row + 1 < maze.length && maze[row + 1][col] == 0 && 0 == scoreArr[row + 1][col]){
                path.push([row + 1, col]);
                queue.push(path);
            }
            //west
            if (0 < col && maze[row][col - 1] == 0 && 0 == scoreArr[row][col - 1]) {
                path.push([row, col - 1]);
                queue.push(path);
            }
            //east
            if (col + 1 < maze[0].length && maze[row][col + 1] == 0 && 0 == scoreArr[row][col + 1]) {
                path.push([row, col + 1]);
                queue.push(path);
            }
        }
        count++;
    }

    return resultPath;
};
let result = solution([[0, 0, 0, 0], [1, 1, 1, 0], [0, 0, 0, 0], [0, 1, 1, 1],[0, 0, 0, 0]]);