[프로그래머스 / JS] 게임 맵 최단거리 - Level 2

🚩 문제 주소

 

📄 접근 방법

 

그래프 탐색 - BFS

 

이 문제에 풀이 방법은 격자판이 주어지는 탐색 문제를 BFS로 푸는 흔한 풀이법과 거의 비슷합니다.

다른 부분은 방문 체크 배열을 확인만 하는 용도로 사용하지 않고, 현재 위치의 숫자에 1을 더한 숫자를 다음에 가야 하는 위치에 업데이트 하는 방식으로 사용합니다.

 

다음 위치의 숫자가 0이라면 방문한 적이 없는 것이므로 업데이트가 되지만, 0이 아니라면 방문한 적이 있는 것이므로

현재 위치 + 1 으로 값을 업데이트합니다.

 

주어진 게임 맵

로직이 처리된 후 게임 맵

 

---

👨‍💻 나의 코드

function solution(maps) {
    const moves = [[0,1],[0,-1],[1,0],[-1,0]];
    const WIDTH = maps[0].length;
    const HEIGHT = maps.length;
    const visited = Array.from({length: HEIGHT}, ()=>Array(WIDTH).fill(0))
    
    const BFS = (a, b) => {
        const q = [];
        q.push([a, b]);
        visited[a][b] = 1;
        while (q.length) {
            const [r, c] = q.shift();
            for (const move of moves) {
                const nr = r + move[0];
                const nc = c + move[1];
                if (nr < 0 || nr >= HEIGHT || nc < 0 || nc >= WIDTH || maps[nr][nc] === 0 || 
                    visited[nr][nc] !== 0) continue;
                visited[nr][nc] = visited[r][c] + 1;
                q.push([nr,nc]);
            }
        }
    }
    BFS(0,0);
    const answer = visited[HEIGHT-1][WIDTH-1];
    return answer === 0 ? -1 : answer;
}