[Algorithm] 게임 맵 최단거리

문제설명

게임 맵 최단거리는 벽이 없는 길 중 목표에 접근할 수 있는 최단 루트를 찾아 이동한 칸의 수를 반환하는 문제다.

이 전에 부트캠프 과정에서 비슷한 알고리즘의 풀이를 본 적이 있었지만 완전 잊은 상태로 다시 풀게 됐다.

두가지의 문제해결 알고리즘을 사용하여 답을 찾아야 했다.

### BFS(너비 우선 탐색)

두 노드 사이의 최단 경로 혹은 임의의 경로를 찾고 싶을 때 이 방법을 선택한다.

BFS는 방문한 노드들을 차례로 저장한 후 꺼낼 수 있는 자료 구조인 큐(Queue)를 사용한다. 선입 선출의 구조

깊이가 1인 모든 노드를 방문하고 나서 그 다음에는 깊이가 2인 모든 노드를, 그 다음에는 깊이가 3인 모든 노드를 방문하는 식으로 계속 방문하다가 더 이상 방문할 곳이 없으면 탐색을 마친다.

문제해결

주어진 maps(2차원 배열)의 길이는 가로(maps.length ) = n, 세로(maps[0].length) = m로 할당한다.

시작 포인트는 [{x : 0, Y : 0}], 타겟이 되는 마지막 포인트는 [{x : n - 1, y : m - 1}]이다.

각 포인트는 [-1 , 1, -1 , 1]로 상하좌우 이동만이 가능하며 시작점부터 조건에 일치하는 이동 가능한 노드를 찾으며 현재 노드를 저장하는 배열 current에 이동한 값을 저장 한 후 maps의 모든 포인트의 방문여부를 boolean(false)로 저장한 visited 배열에 방문 여부를 확인한다.

function solution(maps) {
    // 맵의 세로
    const n = maps.length;
    // 맵의 가로
    const m = maps[0].length;
    // 전체 맵의 방문 여부: 초기값 false
    const visited = new Array(n).fill(false).map(() => new Array(m).fill(false));
    // 좌우 이동 좌표
    const dx = [-1, 1, 0, 0];
    // 상하 이동 좌표
    const dy = [0, 0, -1, 1];
    // 현재 좌표와 길이를 저장하는 객체 배열 생성
    const current = [{x:0, y:0, distance: 1}]
    // start point 설정
    visited[0][0] = true;
    // current 배열의 요소가 없을 때까지 반복해서 길을 찾는다
    while (current.length > 0) {
        //가장 최근 좌우 좌표와 상하 좌표, 이동 거리를 선입 선출한 후 구조 분해 할당한다
        const {x, y, distance} = current.shift();
        // 타겟을 찾은 경우 총 거리를 반환한다.
        if (x === n - 1 && y === m - 1) return distance;
        // 타겟을 찾지 못한 경우 상하 좌우로 이동 가능한 길을 찾는다.
        for (let i = 0; i < 4; i++) {
            const nx = x + dx[i];
            const ny = y + dy[i];
            // 이동한 가로, 세로 축이 맵을 벗어난 경우 혹은 벽에 막혔을 경우
            if (nx < 0 || ny < 0 || nx >= n || ny >= m || maps[nx][ny] === 0) {
                // 이동 불가능한 값을 버리고 다음 길을 찾는다.
                continue;
            }
            // 이동 가능한 길이 미방문한 길이면
            if (!visited[nx][ny]) {
                // current배열에 새로운 길을 입력하고
                current.push({x : nx, y : ny, distance: distance + 1})
                // 방문을 표시한다.
                visited[nx][ny] = true;
            }
        }
    }
    // 모든 길을 방문했음에도 타겟을 찾지 못하면 -1 반환
    return -1;
}

const test1 = [
               [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]
              ]
solution(test1) // 11
const test2 = [
               [1, 0, 1, 1, 1],
               [1, 0, 1, 0, 1],
               [1, 0, 1, 1, 1],
               [1, 1, 1, 0, 0],
               [0, 0, 0, 0, 1]
              ]
solution(test2) // -1