게임 맵 최단거리 ( Level 2, JavaScript, 찾아라 프로그래밍 마에스터 )

게임 맵 최단거리 ( Level 2 )

Programmers 찾아라 프로그래밍 마에스터 ( JavaScript )

문제 링크

 

나의 풀이

function solution(s) {
    const dx = [0,0,1,-1];
    const dy = [1,-1,0,0];
    const queue = [[0,0,1]];

    while ( queue.length ) {
        const cur = queue.shift();
        if ( cur[0] === maps.length - 1 && cur[1] === maps[0].length - 1) 
            return cur[2]
        for(let i=0;i<4;i+=1){
            const yy = cur[0] + dy[i]
            const xx = cur[1] + dx[i]
            if(xx >= 0 && yy >= 0 && xx < maps[0].length && yy < maps.length && maps[yy][xx] === 1 ) {
                maps[yy][xx] = 0;
                queue.push([yy, xx, cur[2] + 1]);    
            }
        }
    }
    return -1
}

최단거리: bfs

1. 시작 좌표 [0,0]과 count인 1을 한 배열에 담아 queue에 삽입
2. 반복문을 통해 큐의 앞에서 하나씩 빼서 탐색
3. 좌표가 1일 경우 ( 길이 뚫린 경우 ) 상하좌우 확인 후 좌표의 값이 1이라면 큐에 삽입
4. 좌표가 맵의 가장 오른쪽 아래까지 갔다면 길을 끝까지 찾았다는 뜻이므로 count값인 cur의 두 번째 인덱스를 리턴
5. 벽으로 막혀 끝까지 가지 못했다면 반복문을 빠져나와 -1을 리턴