[BFS/javascript] 프로그래머스 게임 맵 최단거리

최단거리는 BFS로

 

 

function solution(maps) {
    let answer = 1; // 최단 경로 길이를 저장하는 변수
    let visited = maps; // 방문 여부
    let queue = []; // BFS는 큐
    const dx = [-1, 1, 0, 0]; // x 방향 상하좌우
    const dy = [0, 0, -1, 1]; // y 방향 상하좌우
    const n = maps.length; // 맵의 행 수
    const m = maps[0].length; // 맵의 열 수
    
    queue.push([0, 0]); // 시작 지점을 큐에 추가
    visitied[0][0] = 0; // 시작 지점을 방문한 것으로 표시
    
    while (queue.length > 0) { // 큐가 빌 때까지 반복
        let size = queue.length;
        
        for(let i = 0; i < size; i++) { // 큐에 있는 모든 위치에 대해
            let [x, y] = queue.shift(); // 큐에서 위치 추출
            
            for(let j = 0; j < 4; j ++) { // 상하좌우 4방향에 대해 탐색
                let nx = x + dx[j]; // 현재 위치 + 변화량
                let ny = y + dy[j];
                
                if(nx >= 0 && nx < n && ny >= 0 && ny < m && visited[nx][ny] === 1) { // 유효한 위치인지 방문하지 않았는지 확인
                    if(nx === n - 1 && ny === m - 1) { // 목표 지점에 도달한 경우
                        return ++answer; // 최단 경로 길이를 증가하고 반환         
                    }
                    queue.push([nx, ny]); // 다음 위치를 큐에 추가
                    visited[nx][ny] = 0; // 다음 위치를 방문한 것으로 표시
                }
            }
        }
        answer++; // 현재 스텝에서 다음 스텝으로 이동 
    }
    return -1; // 목표 지점에 도달하지 못한 경우 -1 반환
}