[프로그래머스] 게임 맵 최단거리 - JavaScript

📌 문제

https://programmers.co.kr/learn/courses/30/lessons/1844

📌 풀이

function solution(maps) {
    let answer = 0;
    let n = maps.length - 1, m = maps[0].length - 1;
    let dx = [-1, 0, 1, 0], dy = [0, 1, 0, -1];
    let routes = [], count = 1;
    
    function DFS(x, y) {
        if(x === n && y === m) {
            routes.push(count);
        } else {
            for(let i = 0; i < 4; i++) {
                let nx = x + dx[i];
                let ny = y + dy[i];

                if(nx >= 0 && nx <= n && ny >= 0 && ny <= m && maps[nx][ny] === 1) {
                    maps[nx][ny] = 0;
                    count++;
                    DFS(nx, ny);
                    maps[nx][ny] = 1;
                    count--;
                }
            }
        }
    }
    
    maps[0][0] = 0;
    DFS(0, 0);
    
    if(routes.length) {
        answer = Math.min(...routes);
    } else {
        answer = -1;
    }
    
    return answer;
}

/*
[테스트케이스 실행 결과]
정확성: 69.9
효율성: 0.0
합계: 69.9 / 100.0
*/

dfs가 아닌 bfs로 풀어야 한다구 한다구 한다구 한다 இ௰இ
최단거리를 구할땐 bfs !!

다른 분의 풀이

function solution(maps) {
    let answer = 1;
    let visited = maps;
    let queue = [];
    const dx = [-1, 1, 0, 0];
    const dy = [0, 0, -1, 1];
    const n = maps.length;
    const m = maps[0].length;
    
    queue.push([0, 0]);
    visited[0][0] = 0;
    
    while(queue.length > 0) {
        let size = queue.length;
        
        for(let i = 0; i < size; i++) {
            let [x, y] = queue.shift();
            
            for(let j = 0; j < 4; j++) {
                let nx = x + dx[j];
                let ny = y + dy[j];
                
                if(nx >= 0 && nx < n && ny >= 0 && ny < m && visited[nx][ny] === 1) {
                    if(nx == n - 1 && ny == m - 1) {
                        return ++answer;
                    }
                    queue.push([nx, ny]);
                    visited[nx][ny] = 0;
                }
            }
        }
        answer++;
    }
    
    return -1;
}

참고
(프로그래머스 JS)게임 맵 최단거리