[JS][프로그래머스 Lv2]게임 맵 최단거리

프로그래머스 Lv2 게임 맵 최단거리

* 문제설명

캐릭터가 상대 팀 진영에 도착하기 위해서 지나가야 하는 칸의 최솟값 return. 단 상태 팀 진영에 도착할 수 없을 때는 -1 return.

---

* 해결방법

• 최단거리는 너비우선탐색(bfs)가 적절 (stack 보다는 queue 사용)
• 현재 위치에서 상하좌우 이동 가능 여부 판단
• 상하좌우가 벽(0)이거나, 행렬의 범위를 벗어났다면 이동불가.
• 이동할 수 있다면 이동할 좌표와 이동할 횟수를 큐에 추가
• FIFO를 따라 BFS 함수의 Queue에서 좌표 (x,y)가 (n, m)와 같다면 바로 BFS 함수를 종료하고 최단경로를 출력한다.
• Queue에 원소가 존재하지 않을 때 까지 (x,y)가 (n, m)에 도달하지 못했다면 -1을 출력한다.

* 작성코드

function solution(maps) {
    // 1. 남동북서 기준
    const dy = [1,0,-1,0];
    const dx = [0,1,0,-1];
    const row = maps.length;
    const col = maps[0].length;

    // 2. map 생성
    const visitCount = [...maps].map((r) => r.map((c) => 1));

    // 3. queue에 원소 존재 x시 도달 못하면 -1 반환
    const queue = [[0,0]];  //시작점

    // 4. queue길이가 0 이면 stop
    while(queue.length) {
        const [y, x] = queue.shift();

        // 5. 상하좌우 확인
        for(let i = 0; i < 4; i++ ) {
            const ny = y + dy[i];
            const nx = x + dx[i];

            // 6. 좌표가 주어진 map 안에 있는지 확인
            if(ny >= 0 && nx >= 0 && ny < row && nx < col) {
                // 7.
                if(maps[ny][nx] === 1 && visitCount[ny][nx] === 1) {
                    visitCount[ny][nx] = visitCount[y][x] + 1;
                    queue.push([ny,nx]);
                }
            }
        }
    }

    return visitCount[row - 1][col - 1] === 1 ? -1 : visitCount[row - 1][col - 1];    
}