프로그래머스 - 리코쳇로봇

문제 

이동 규칙이 벽을 만날 때까지 한 방향으로 계속 움직이는 리코셰 로봇이라는 보드게임이 있다.

시작 지점에서 골인지점까지 최소로 이동하여 도착했을 때의 움직인 횟수를 리턴하면 된다.

도착하지 못하는 경우에는 -1을 리턴한다.

 

내 풀이

목적지에 도달했을 때 최소 이동횟수를 보장하기 위해서  BFS를 이용하여 문제를 해결하였다.

문제를 해결하기 위해 크게 시작 지점을 구하는 함수 , 로봇을 움직이는 함수 , BFS 를 실행하는 부분으로 나눠 문제를 해결하였다.

 

시작 지점을 구하는 함수

const findStartPosition = () =>  {
    let start;
    boardArr.forEach((row , i)=>{
        const rFind = row.indexOf('R');
        if(rFind !== -1){
            start = [i , rFind]
        }
    });
    return start
}

 

로봇을 움직이는 함수

다른 문제와 차별점이 되는 부분이다.

다음 위치가 경계나 벽이 아니라면 현재 위치를 다음 위치로 이동시켜 벽이나 경계를 만날때까지 이동시킨다

const moveRobot = (x, y, direction) => {
    const [dx, dy] = move[direction];
    let currentX = x;
    let currentY = y;

    while (true) {
        const nextX = currentX + dx;
        const nextY = currentY + dy;

        if (nextX < 0 || nextX >= height || 
            nextY < 0 || nextY >= width || 
            boardArr[nextX][nextY] === 'D') {
            return [currentX, currentY];
        }

        currentX = nextX;
        currentY = nextY;
    }
}

BFS 시행 코드

로봇의 위치를 queue에 넣어  bfs를 시행한다.
현재 위치에서 상하좌우로 이동하였을 때의 위치와 움직인 횟수를 queue에 다시 push 하여 목표 지점에 도달할 때까지 반복한다.

같은 장소에 도달하여 무한루프에 빠지는 경우와 중복을 제거하기 위해 visit 배열을 사용하였다.

const start = findStartPosition(); 
queue.push([...start, 0]);
visit[start[0]][start[1]] = true;  // 초기 위치 방문 체크
while(queue.length){
    const [x, y, cnt] = queue.shift(); 
    if(boardArr[x][y] === 'G'){
        return cnt;
    }

    for(const dir of direction){
        const [nx, ny] = moveRobot(x,y,dir);
        if (!visit[nx][ny]) {
            visit[nx][ny] = true;
            queue.push([nx, ny, cnt + 1]);
        }
    }
}

전체코

function solution(board) {
    const boardArr = Array.from(board, (el) => el.split(''))
    const visit = boardArr.map((el)=> el.map(_=> false))
    const direction = ["up" , "right" , "left" , "down"];
    const move = { "up": [-1, 0], "right": [0, 1], "left": [0, -1], "down": [1, 0] };
    const queue = [];
    const width = boardArr[0].length;
    const height = boardArr.length;
    
    const findStartPosition = () =>  {
        let start;
        boardArr.forEach((row , i)=>{
            const rFind = row.indexOf('R');
            if(rFind !== -1){
                start = [i , rFind]
            }
        });
        return start
    }
    
  const moveRobot = (x, y, direction) => {
    const [dx, dy] = move[direction];
    let currentX = x;
    let currentY = y;

    while (true) {
        const nextX = currentX + dx;
        const nextY = currentY + dy;

        if (nextX < 0 || nextX >= height || 
            nextY < 0 || nextY >= width || 
            boardArr[nextX][nextY] === 'D') {
            return [currentX, currentY];
        }

        currentX = nextX;
        currentY = nextY;
    	}
	}
    
  
    const start = findStartPosition(); 
    queue.push([...start, 0]);
    visit[start[0]][start[1]] = true;  // 초기 위치 방문 체크
    
    while(queue.length){
        const [x, y, cnt] = queue.shift(); 
        if(boardArr[x][y] === 'G'){
            return cnt;
        }
        
        for(const dir of direction){
            const [nx, ny] = moveRobot(x,y,dir);
            if (!visit[nx][ny]) {
                visit[nx][ny] = true;
                queue.push([nx, ny, cnt + 1]);
            }
        }
    }
    
    return -1;  // 도달할 수 없는 경우
}

출처 : 프로그래머스

문제 링크 : https://school.programmers.co.kr/learn/courses/30/lessons/169199

프로그래머스