게임 맵 만들기

문제 설명

ROR 게임은 두 팀으로 나누어서 진행하며, 상대 팀 진영을 먼저 파괴하면 이기는 게임입니다. 따라서, 각 팀은 상대 팀 진영에 최대한 빨리 도착하는 것이 유리합니다.
지금부터 당신은 한 팀의 팀원이 되어 게임을 진행하려고 합니다. 다음은 5 x 5 크기의 맵에, 당신의 캐릭터가 (행: 1, 열: 1) 위치에 있고, 상대 팀 진영은 (행: 5, 열: 5) 위치에 있는 경우의 예시입니다.

위 그림에서 검은색 부분은 벽으로 막혀있어 갈 수 없는 길이며, 흰색 부분은 갈 수 있는 길입니다. 캐릭터가 움직일 때는 동, 서, 남, 북 방향으로 한 칸씩 이동하며, 게임 맵을 벗어난 길은 갈 수 없습니다.
게임 맵의 상태 maps가 매개변수로 주어질 때, 캐릭터가 상대 팀 진영에 도착하기 위해서 지나가야 하는 칸의 개수의 최솟값을 return 하도록 solution 함수를 완성해주세요. 단, 상대 팀 진영에 도착할 수 없을 때는 -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) 위치에 있습니다.

입출력 예

maps	answer
[[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
[[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]]	-1

해결한 코드

function solution(maps) {
    var answer = 0;
    const [n,m]= [maps.length, maps[0].length];
    const check = maps.map(i => i.map(v => 0));
    
    const [dx, dy] = [[-1,0,1,0], [0,1,0,-1]];
    const queue = [[0,0]];
    check[0][0] = 1;
    //console.log(queue.shift());
    while(queue.length) {
        var [x,y] = [queue[0][0],queue[0][1]];
        queue.shift();
        for(let i=0;i<4;i++){
            var [nx, ny] = [x+dx[i], y+dy[i]];
            if(nx < 0 || ny < 0 ||nx >=n||ny>=m) continue;
            else if(maps[nx][ny] === 1 && check[nx][ny]===0) { 
                check[nx][ny] = check[x][y]+1;
                queue.push([nx,ny]);
            }
        }
    }
    if(check[n-1][m-1]===0) return -1;
    return check[n-1][m-1];

코드 + 설명

function solution(maps) {
    const [n,m]= [maps.length, maps[0].length];
    //맵의 행과 열 길이 저장
    const check = maps.map(i => i.map(v => 0));
    //check 배열 생성(maps 배열과 동일한 형태이며 각 칸에 누적 이동 수를 담을 예정.
    
    const [dx, dy] = [[-1,0,1,0], [0,1,0,-1]];
    // 이동 방향(상,우,하,좌)순으로 했음
    // for문으로 이 방향 기준으로 돌릴 예정
    
    const queue = [[0,0]];
    //queue에 기준점 추가하고 빼고 반복
    //0,0부터 시작하는 문제니 초기값 넣음
    check[0][0] = 1;
    //queue에 들어간 좌표는 check에 누적 이동 수 입력

    while(queue.length) {
    //기준점인 queue에 원소가 없을 때까지 반복
    //길이가 0이면 false이니 반복문 stop
        var [x,y] = [queue[0][0],queue[0][1]];
        queue.shift();
        //queue 맨 앞에서 꺼내서 기준점(x,y)으로 삼음. 갔던 칸 또 가면 안되니 shift로 아예 빼버림 
        for(let i=0;i<4;i++){ 
        //기준점 기준으로 아까 만들어놓은 상우하좌로 찔러보기
            var [nx, ny] = [x+dx[i], y+dy[i]];
            //기준점(x,y)로부터 이동 가능 위치를 nx,ny로 할당 
            if(nx < 0 || ny < 0 ||nx >=n||ny>=m) continue;
            //이동 가능 위치가 배열을 이탈하면 스킵
            else if (maps[nx][ny] === 1 && check[nx][ny]===0) { 
                check[nx][ny] = check[x][y]+1;
                queue.push([nx,ny]);
                //이동 가능위치가 장애물 없고, 왔던 길이 아니면 check의 해당 위치에 누적이동수 추가하고 queue에 새로운 기준점 push
            }
        }
    }
    if(check[n-1][m-1]===0) return -1;
    //도착지까지 못갔으면 -1반환
    return check[n-1][m-1];
}

comment

이 문제의 포인트는 이동한 각 위치에 누적이동수를 바로 입력하는 것이다.
이동수가 기록된 위치에는 다시 접근을 못하게 설정해놓으면, 최초로 기록된 누적이동수를 출력할 수 있고 이는 곧 최단 거리가 된다.

if(nx===n-1 && ny ===m-1) break;
while문에 위 코드를 넣어 도착지인 maps[n-1][m-1]에 이동했을 때 while문을 바로 멈추려고했는데 queue가 빈배열이 될 때까지 while문을 돌리는 것과 효율성 테스트 결과가 비슷하게 나온다. 어차피 그쯤까지 가면 queue에 남는 게 없어서 그런가? 궁금증이 남는다.