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

문제 내용

maps 배열이 주어짐.(0, 0) 에서 출발해서 (n -1, m-1) 까지 최단거리를 찾아라.

최단거리가 없다면 -1 을 return 해라.

 

제한사항

• maps는 n x m 크기의 게임 맵의 상태가 들어있는 2차원 배열로, n과 m은 각각 1 이상 100 이하의 자연수입니다.
  • n과 m은 서로 같을 수도, 다를 수도 있지만, n과 m이 모두 1인 경우는 입력으로 주어지지 않습니다.
• maps는 0과 1로만 이루어져 있으며, 0은 벽이 있는 자리, 1은 벽이 없는 자리를 나타냅니다.
• 처음에 캐릭터는 게임 맵의 좌측 상단인 (1, 1) 위치에 있으며, 상대방 진영은 게임 맵의 우측 하단인 (n, m) 위치에 있습니다.

---

전체 코드

function solution(maps) {
    // 1. n 과 m 을 설정함
    const n = maps.length;
    const m = maps[0].length;

    // 2. 정답 저장용
    let answer = -1;

    // 3. 방문을 체크할 배열
    let visited = Array.from(Array(n), () => Array(m).fill(false));

    // 4. BFS 를 하기 위한 queue, 초기 값을 저장해둠
    let queue = [[0, 0, 1]];

    // 5. queue 의 위치를 저장할 queueIndex
    let queueIndex = 0;

    // 6. x, y 가 움직일 배열을 저장함 (상, 우, 하, 좌)
    const moveX = [-1, 0, 1, 0];
    const moveY = [0, 1, 0, -1];

    // 7. BFS 진행할 while 문
    while (queue.length > queueIndex) {
        // 8. 일단 queue 에 있는 값을 꺼냄
        const now = queue[queueIndex];
        // 9. 값을 꺼냈으므로 index 를 +1 해줌
        queueIndex += 1;

        // 10. 만약 꺼낸 값이 정답 (도착지) 이면
        if (now[0] == n - 1 && now[1] == m - 1) {
            // 11. answer 에 답을 저장함 (now[2] 는 이동 거리)
            answer = now[2];
            break;
        }

        // 12. 만약 꺼낸 값이 방문하지 않은 값이라면
        if (!visited[now[0]][now[1]]) {
            // 13. 방문
            visit(now[0], now[1], now[2])
        }
    }

    // 14. 방문 함수. x, y 좌표와 count (이동거리) 를 파라미터로 받음
    function visit(x, y, count) {
        // 15. 먼저 방문했다고 체크함
        visited[x][y] = true;

        // 16. 현재 x, y 위치에서 상, 하, 좌, 우 로 이동할 반복문
        for (let i = 0; i < moveX.length; i++) {
            // 17. movedX, Y 로 설정함.
            const movedX = x + moveX[i];
            const movedY = y + moveY[i];

            // 18. 만약, movedX, movedY 가 배열의 범위 안에 있고, 그 값 위치가 아직 방문하지 않았고, 그 위치를 방문할 수 있다면 (값이 1이라면)
            if (movedX >= 0 && movedX < n && movedY >= 0 && movedY < m && !visited[movedX][movedY] && maps[movedX][movedY] == 1) {
                // queue 에 그 값을 넣음
                queue.push([x + moveX[i], y + moveY[i], count + 1]);
            }
        }
    }

    return answer;
}

 

문제의 첫번째 예시를 보면

maps	return
[[1, 0, 1, 1, 1], [1, 0, 1, 0, 1], [1, 0, 1, 1, 1], [1, 1, 1, 0, 1], [0, 0, 0, 0, 1]]	11

이렇게 주어졌다.

 

그림으로 보면

이런 식의 모양이다.

    // 3. 방문을 체크할 배열
    let visited = Array.from(Array(n), () => Array(m).fill(false));

 

maps 와 동일한 크기로 visited 배열을 생성해주었다.

 

    // 4. BFS 를 하기 위한 queue, 초기 값을 저장해둠
    let queue = [[0, 0, 1]];

    // 5. queue 의 위치를 저장할 queueIndex
    let queueIndex = 0;

    // 6. x, y 가 움직일 배열을 저장함 (상, 우, 하, 좌)
    const moveX = [-1, 0, 1, 0];
    const moveY = [0, 1, 0, -1];

그리고 queue 에 초기 값을 넣어주고 해당 queue 의 위치를 나타낼 queueIndex.

또 상, 우, 하, 좌 방향으로 x, y 를 움직일 moveX, moveY 도 만들어줬다.

 

    // 7. BFS 진행할 while 문
    while (queue.length > queueIndex) {
        // 8. 일단 queue 에 있는 값을 꺼냄
        const now = queue[queueIndex];
        // 9. 값을 꺼냈으므로 index 를 +1 해줌
        queueIndex += 1;

        // 10. 만약 꺼낸 값이 정답 (도착지) 이면
        if (now[0] == n - 1 && now[1] == m - 1) {
            // 11. answer 에 답을 저장함 (now[2] 는 이동 거리)
            answer = now[2];
            break;
        }

        // 12. 만약 꺼낸 값이 방문하지 않은 값이라면
        if (!visited[now[0]][now[1]]) {
            // 13. 방문
            visit(now[0], now[1], now[2])
        }
    }

queue 에는 현재 [[0, 0, 1]] 이므로 length 는 1 이고 queueIndex 는 0 이므로 while 문이 진행된다.

먼저 now 값은 [0, 0, 1] 이 되고

queueIndex 를 + 1 해준다.

 

0, 0 은 n - 1, m - 1 이 아니므로 12번이 진행된다.

    // 14. 방문 함수. x, y 좌표와 count (이동거리) 를 파라미터로 받음
    function visit(x, y, count) {
        // 15. 먼저 방문했다고 체크함
        visited[x][y] = true;

        // 16. 현재 x, y 위치에서 상, 하, 좌, 우 로 이동할 반복문
        for (let i = 0; i < moveX.length; i++) {
            // 17. movedX, Y 로 설정함.
            const movedX = x + moveX[i];
            const movedY = y + moveY[i];

            // 18. 만약, movedX, movedY 가 배열의 범위 안에 있고, 그 값 위치가 아직 방문하지 않았고, 그 위치를 방문할 수 있다면 (값이 1이라면)
            if (movedX >= 0 && movedX < n && movedY >= 0 && movedY < m && !visited[movedX][movedY] && maps[movedX][movedY] == 1) {
                // queue 에 그 값을 넣음
                queue.push([x + moveX[i], y + moveY[i], count + 1]);
            }
        }
    }

일단 이렇게 시작을 한다.

0, 0 을 방문했다고 체크를 하고 (15 번)

현재 위치에서 이동할 수 있는 지 확인하고 이동할 수 있다면 queue 에 값을 집어넣는다.

queue 에 [1, 0, 2] 가 저장되었고 visited[0][0] = true 가 된 모습이다.

 

동일하게 진행하면 visit(2, 2, 7) 이 불리고

저장할 때 상, 우, 하, 좌 순으로 저장 (6번) 을 하기 때문에 

이렇게 저장이 되어있다면

[1, 2, 8] 먼저 진행하고 그 다음에 [2, 3, 8] 을 진행한다.

쭉 진행하게 되면

[3, 4, 10] 이 진행이 되고

그 다음에 [0, 4, 11], 그리고 [4, 4, 11] 진행되면서 10 번 (now[0], [1] = n-1, m-1) 이 해당하면서

answer 에 답을 갱신하고 종료된다.

---

결론

BFS 로 쉽게 풀 수 있다.

상, 우, 하, 좌 순으로 반복하는 것 보다 우, 하 를 먼저 반복하는게 더 시간이 짧게 걸리지 않을까 생각한다. (목적지가 우측 하단에 있으므로??)

 

상, 우, 하, 좌 순

하, 우, 좌, 상 순

별 차이 없는 듯

 

 

출처 : 프로그래머스 찾아라 프로그래밍 마에스터 게임 맵 최단거리

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

코딩테스트 연습 - 게임 맵 최단거리