[프로그래머스] 리코쳇 로봇 ( js)

문제 설명

리코쳇 로봇이라는 보드게임이 있습니다.

이 보드게임은 격자모양 게임판 위에서 말을 움직이는 게임으로, 시작 위치에서 출발한 뒤 목표 위치에 정확하게 멈추기 위해 최소 몇 번의 이동이 필요한지 말하는 게임입니다.

이 게임에서 말의 이동은 현재 위치에서 상, 하, 좌, 우 중 한 방향으로 게임판 위의 장애물이나 게임판 가장자리까지 부딪힐 때까지 미끄러져 움직이는 것을 한 번의 이동으로 정의합니다.

다음은 보드게임판을 나타낸 예시입니다. ("."은 빈 공간을, "R"은 로봇의 처음 위치를, "D"는 장애물의 위치를, "G"는 목표지점을 나타냅니다.)

...D..R
.D.G...
....D.D
D....D.
..D....
이때 최소 움직임은 7번이며 "R" 위치에서 아래, 왼쪽, 위, 왼쪽, 아래, 오른쪽, 위 순서로 움직이면 "G" 위치에 멈춰 설 수 있습니다.

게임판의 상태를 나타내는 문자열 배열 board가 주어졌을 때, 말이 목표위치에 도달하는데 최소 몇 번 이동해야 하는지 return 하는 solution함수를 완성해주세요. 만약 목표위치에 도달할 수 없다면 -1을 return 해주세요.

제한 사항
3 ≤ board의 길이 ≤ 100
3 ≤ board의 원소의 길이 ≤ 100
board의 원소의 길이는 모두 동일합니다.
문자열은 ".", "D", "R", "G"로만 구성되어 있으며 각각 빈 공간, 장애물, 로봇의 처음 위치, 목표 지점을 나타냅니다.
"R"과 "G"는 한 번씩 등장합니다.
입출력 예
board result
["...D..R", ".D.G...", "....D.D", "D....D.", "..D...."] 7
[".D.R", "....", ".G..", "...D"] -1
입출력 예 설명
입출력 예 #1
문제 설명의 예시와 같습니다.
입출력 예 #2
.D.R
....
.G..
...D
"R" 위치에 있는 말을 어떻게 움직여도 "G" 에 도달시킬 수 없습니다.
따라서 -1을 return 합니다.

처음 풀이 (통과 X ) 

function solution(board) {
    // 도착 지점 좌표랑 출발 지점 좌표 구하기 만약 도착지점 좌표 근처에 벽이나 가장자리 없으면 -1 
    let answer = 0;
    let start = [];
    let finish = [];
    let finishNear = [];
    let checkD = 0;
    
    for(let i =0; i<board.length; i++){
        for(let j =0; j<board[i].length; j++){
            if(board[i][j] === 'R'){
                start.push(i);
                start.push(j);
            }
            if(board[i][j] === 'G'){
                finish.push(i);
                finish.push(j);
                finishNear.push([i+1,j]);
                finishNear.push([i-1,j]);
                finishNear.push([i,j+1]);
                finishNear.push([i,j-1]);
                
            }
        }
    }
    // 도착지 주변에 장애물이 없으면 어떻게 움직여도 G에 도달 못하므로 미리 처리하기 위함 
    finishNear.forEach((pos)=>{
        let [x,y] = pos;
        if(board[x][y] === 'D') checkD++;
    })
    if(checkD < 1) return -1;
    
    function findDorWalls(x, y, dir){
        if(dir === 'L'){
            for(let i = y ; y >=0 ; y--){
                if( board[x][i] === 'D'){
                    return [x , i+1];
                }
            }
            return [x , 0]; // 장애물이 없으면 벽에 닿은 것 
        } else if( dir === 'R'){
            for(let i = y ; y < board[x].length ; y++){
                if( board[x][i] === 'D'){
                    return [x , i-1];
                }
            }
            return [x, board[x].length-1]
        } else if( dir = 'U'){
            for(let i = x ; x >=0 ; x--){
                if(board[i][y] === 'D'){
                    return [i+1, y];
                }
            }
            return [0, y];
        } else {
            for(let i = x ; x <board.length ; x++){
                if( board[i][y] === 'D'){
                    return [i-1, y];
                }
            }
            return [board.length-1, y];
        } 
        
    }
    
    let queue = [[start[0],start[1], 0]];
   
    while(queue.length){
        let [px, py , count] = queue.shift();
        if(px === finish[0] && py === finish[1]){
            answer = count;
            break;
        }
        if(py-1 >=0 && board[px][py-1] ==='.'){
            let ans = findDorWalls(px,py,'L');
            queue.push([ans[0],ans[1],count+1]);     
        }
        if(py+1 < board[px].length && board[px][py+1] ==='.'){
            let ans = findDorWalls(px,py,'R');
            queue.push([ans[0],ans[1],count+1]);;
        }
       
        if(px-1 >=0 && board[px-1][py] ==='.') {
            let ans = findDorWalls(px,py,'U');
            queue.push([ans[0],ans[1],count+1]);
        }
        
        if(px+1 < board.length && board[px+1][py] === '.'){
            let ans = findDorWalls(px,py,'D');
            queue.push([ans[0],ans[1],count+1]);
        }
        
        
    }
    
    return answer;
}

 

시간초과로 통과하지도 못하고 너무 반복적인 코드가 많다.. 일단 문제점으로 visited배열을 선언을 안해줘서 계속 왔던 곳도 방문해서 시간초과가 났던 것 같다. 
그래서 수정한 코드에는 visited 배열을 추가해주고 , 추가적으로 불필요하게 반복되는 코드를 깔끔하게 합쳤다. 

 

통과한 풀이 

function solution(board) {
    const rows = board.length;
    const cols = board[0].length;
    const directions = [
        [-1, 0], 
        [1, 0], 
        [0, -1], 
        [0, 1]   
    ];
    
    let start = null;
    let finish = null;

    // 시작점과 도착점 찾기
    for (let i = 0; i < rows; i++) {
        for (let j = 0; j < cols; j++) {
            if (board[i][j] === 'R') start = [i, j];
            if (board[i][j] === 'G') finish = [i, j];
        }
    }

    const isValid = (x, y) => x >= 0 && x < rows && y >= 0 && y < cols;
    const findEdge = (x, y, dx, dy) => {
        while (isValid(x + dx, y + dy) && board[x + dx][y + dy] !== 'D') {
            x += dx;
            y += dy;
        }
        return [x, y];
    };

    const visited = Array.from({ length: rows }, () => Array(cols).fill(false));
    const queue = [[...start, 0]]; // [x, y, count]
    visited[start[0]][start[1]] = true;

    while (queue.length) {
        const [x, y, count] = queue.shift();

        if (x === finish[0] && y === finish[1]) return count;

        for (const [dx, dy] of directions) {
            const [nx, ny] = findEdge(x, y, dx, dy);

            if (!visited[nx][ny]) {
                visited[nx][ny] = true;
                queue.push([nx, ny, count + 1]);
            }
        }
    }

    return -1; 
}

 

수정한 코드를 간단하게 설명하자면 

1. 초기 설정: 시작점 R과 도착점 G를 찾고, BFS 탐색을 위한 큐와 방문 체크 배열을 초기화 
2. 끝까지 이동: 현재 위치에서 해당 방향으로 장애물이나 벽에 닿을 때까지 이동하는 findEdge 함수를 생성
3. BFS 탐색: 큐에서 위치를 꺼내 네 방향으로 이동 가능한 경로를 탐색하며, 새로운 위치를 큐에 추가
4. 방문 체크: 이미 방문한 위치는 다시 탐색하지 않도록 방문 배열을 활용해 중복 탐색을 방지
5. 결과 반환: 도착점에 도달하면 이동 횟수를 반환하고, 불가능하면 -1을 반환