게임 맵 최단거리

게임 맵 최단거리

문제

게임 맵의 상태 maps가 매개변수로 주어질 때, 캐릭터가 상대 팀 진영에 도착하기 위한 최단거리를 리턴해야 함. 다만 목적지에 도착이 불가능할 경우, -1을 리턴해야 함.

• 조건

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

문제의 핵심

• BFS(Breadth-First Search)
  너비 우선 탐색을 통해 노드에서 인접한 노드를 먼저 탐색하여 최단거리를 알아 낼 수 있다!

예시) map = [[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]]

function solution(maps) {
    
    // maps 구조 = [Y좌표][X좌표]
    const yLen = maps.length;
    const xLen = maps[0].length;
    
    // 목적지 좌표 설정
    const destY = yLen - 1;
    const destX = xLen - 1;
    
    // 한 칸씩 이동할 수 있는 X, Y 배열 셋팅
    const mY = [0, 0, 1, -1];
    const mX = [-1, 1, 0, 0];
    
    // 현재 위치(Y, X) & 이동거리를 저장할 수 있는 queue 셋팅
    let queue = [[0, 0, 1]];
    
    while(queue.length) {
        
        // 현재 위치(Y, X) & 이동거리
        let [curY, curX, move] = queue.shift();
        
        // 현재 위치가 목적지와 같을 때 이동거리 출력
        if(curY === destY && curX === destX) return move;
        
        // mY, mX 순환
        for(let i = 0; i < 4; i++){
            
            // 현재 방문 중인 위치(Y,X)
            let visitedY = curY + mY[i];
            let visitedX = curX + mX[i];
            
            // 방문 위치가 좌표 안에 있는지 && 위치가 갈 수 있는 길인지
            if(visitedY >= 0 && visitedY < yLen && visitedX >= 0 && visitedX < xLen && maps[visitedY][visitedX] === 1) {
                queue.push([visitedY, visitedX, move + 1]);
                // 방문 처리
                maps[visitedY][visitedX] = 0;
            }
        }
    }
    return -1;
}