[프로그래머스] Level2 - 리코쳇 로봇(Javascript)

프로그래머스

📝문제 요약

1️⃣ 이 보드게임은 격자모양 게임판 위에서 말을 움직이는 게임으로, 시작 위치에서 목표 위치까지 최소 몇 번만에 도달할 수 있는지 말하는 게임이다.

2️⃣ 말의 움직임은 상, 하, 좌, 우 4방향 중 하나를 선택해서 게임판 위의 장애물이나 맨 끝에 부딪힐 때까지 미끄러져 이동하는 것을 한 번의 이동으로 친다.

3️⃣ 말이 목표위치에 도달하는데 최소 몇 번 이동해야 하는지 return하는 solution 함수를 완성해라.

 

📚 중요 포인트

1️⃣ 게임판 위의 장애물이나 맨 끝에 부딪힐 때까지 미끄러져 이동하는 것을 한 번의 이동으로 친다.

2️⃣ 장애물을 만나거나 벽을 만날때까지 미끄려져 이동한다고 했으니 한 번 이동은 한 방향으로 계속 이동시키고 벽이나 장애물을 만났을 때 멈추는 것을 의미한다. 그 때 그 자리가 G라면 목표 위치에 도달한 것이다.

3️⃣ BFS 방식으로 문제를 해결했다.

 

✅ 정답 코드

function solution(board) {
    // 한 배열의 길이
    const x_max = board[0].length;
    // 전체 배열의 길이
    const y_max = board.length;
    // 사방탐색
    const direction = [[-1, 0], [1, 0], [0, -1], [0, 1]];
    // 방문했는지 체크하기 
    let visited = Array.from({length: y_max}, () => Array(x_max).fill(-1));
    
    // 이동함수
    function move(d, y, x) {
    	// 조건이 참이면 계속 돌기
        while (true) {
            // 현재 방향에서 사방탐색
            let newY = y + d[0];
            let newX = x + d[1];
            
            // 유효하지 않은 범위이거나 장애물을 만나면 탐색 이전 위치를 return 해준다.
            if (newX < 0 || newY < 0 || newX >= x_max || newY >= y_max || board[newY][newX] === "D") {
               return [y, x]; 
            }
            // 그렇지 않으면 다음 위치로 이동
            y = newY;
            x = newX;
        }
    }
    
    // bfs 함수
    function bfs() {
        // 다음 위치를 담을 배열 선언
        let queue = [];
        // 최종위치를 담기 위한 변수
        let final_y = 0, final_x = 0;
        
        // 배열의 크기만큼 2중 반복문을 돌면서
        for (let y = 0; y < y_max; y++) {
            for (let x = 0; x < x_max; x++) {
                // 만약에 시작지점이면
                if (board[y][x] === "R") {
                    // 배열에 현재 위치를 넣어주고
                    queue.push([y, x]);
                    // 방문표시한다.
                    visited[y][x] = 0; 
                }
                // 만약에 목표지점에 도달한다면
                if (board[y][x] === "G") {
                    // 최종 지점을 변수에 담아준다.
                    final_y = y;
                    final_x = x;
                }
            }
        }
        
        // 배열에 좌표가 있을때까지 while문을 돌려준다.
        while (queue.length > 0) {
            // 가장 최근 좌표를 꺼내주고
            let [y, x] = queue.shift();
            // 최근 자표에서 사방탐색을 진행한다.
            for (let d of direction) {
                let [ny, nx] = move(d, y, x)
                // 만약에 다음 좌표가 방문한 적이 없다면
                if (visited[ny][nx] == -1) {
                    // 다음 방문할 곳으로 넣어주고
                    queue.push([ny, nx]);
                    // 현재 거리를 갱신해준다.
                    visited[ny][nx] = visited[y][x] + 1;
                }
            }
        }
        // 최종적으로 목표지점을 return한다. 도달할 수 없으면 자동으로 -1이 return 된다. 
        return visited[final_y][final_x];
    }
    // bfs 함수를 실행한다.
    return bfs();
}