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

 

문제

 

풀이

큐에 x, y의 좌표값과 방문한 칸의 개수 answer을 초기값으로 각각 0, 0, 1씩 넣어준다

큐에 현재 좌표의 상하좌우의 좌표값과 answer+1이 든 배열을 push해준다

shift()로 큐에서 하나씩 빼내서 해당 좌표가 갈 수 없는 길이라면 다음 요소를 확인하고 갈 수 있는 길이라면 큐에 남은 요소가 없어질 때 까지 이 과정을 반복한다

반복하는 과정중 x, y 좌표가 상대 진영에 도달하면 answer을 리턴한다

큐에 남은 요소가 없어진다면 상대 진영에 도착하지 못한다는 의미이기에 -1을 리턴한다

function solution(maps) {
    let xLength = maps[0].length;
    let yLength = maps.length;
    let xGoal = xLength-1;
    let yGoal = yLength-1;
    
    let queue = [];
    // queue의 초기값으로 y, x 값과 (0, 0)은 방문했기 때문에 리턴할 answer은 1로 둔다
    queue.push([0, 0, 1]);
    
    while(queue.length) {
        // queue에 있는 요소 꺼내기
        let [y, x, answer] = queue.shift();
        
        // x값이 0보다 작거나 xLength보다 길다면 즉, maps에 없는 좌표면 while문 조건식으로 이동
        if(x < 0 || x >= xLength) continue;
        // y값이 0보다 작거나 yLength보다 길다면 즉, maps에 없는 좌표면 while문 조건식으로 이동
        if(y < 0 || y >= yLength) continue;
        // maps[y][x]값이 0이라면 즉, 갈 수 없는 길이라면 while문 조건식으로 이동
        if(maps[y][x] === 0) continue;
        
        // x와 y값이 상대팀 진영에 도착했다면 answer 리턴
        if(x === xGoal && y === yGoal) {
            return answer;
        }
        
        // 방문한 좌표 0으로 바꿈
        maps[y][x] = 0;
        
        // queue에 현재 좌표의 상하좌우 각각의 좌표와 answer+1 푸쉬
        queue.push([y+1, x, answer+1]);
        queue.push([y, x+1, answer+1]);
        queue.push([y-1, x, answer+1]);
        queue.push([y, x-1, answer+1]);
    }
    
    // while문이 끝났다면 갈 곳이 없다는 의미이므로 -1 리턴
    return -1;
}