[프로그래머스] Lv2. 게임 맵 최단거리 - JavaScript

문제분류 : 코팅테스트 연습

난이도 : Level 2

출처 : 프로그래머스 - 게임 맵 최단거리

문제

제한사항

📌 내가 생각한 풀이

전형적인 BFS문제이다. 가능한 경로를 체크한뒤 큐에 넣어서 경로를 탐색해주자.

function solution(maps) {
    var answer = 0;
    let count = 1;
    let q = [];
    let saero = maps.length;
    let garo = maps[0].length;
    //하 상
    let dx = [-1,1,0,0];
    //우 좌
    let dy = [0,0,1,-1];
    q.push([0,0]);
    maps[q[0][0]][q[0][1]] = 0;
    while(q.length){
        let size = q.length;
        for(var j =0; j<size; j++){
            let [x,y] = q.shift();
            for(var i = 0; i<4; i++){
                let nx = x + dx[i];
                let ny = y + dy[i];
                
                if(nx >= 0 && nx<saero && ny >= 0 && ny < garo && maps[nx][ny] === 1){
                    maps[nx][ny] = 0;
                    q.push([nx,ny]);
                }
                if(nx === saero-1 && ny === garo-1) return count+1
                

            }
        }
        
        count++;
    }
    return -1
    
}

📌 느낀점

경로찾기 BFS문제이다. 여기서 주의할 점은 size를 q.length로 잡아서 size만큼 반복해주는 것 이다. 그래야 q.length만큼 다 돈뒤 count++이 되기 떄문이다.