[프로그래머스/level2/JS] 리코쳇 로봇

문제링크

프로그래머스 리코쳇 로봇

문제풀이

문제를 읽었는데 뭔가 많이 익숙하네? 그렇다. 어렸을 때 컴퓨터실에서 다들 한번쯤 해보셨을 게임 포켓몬스터 골드의 동굴탈출(?) 문제이다. 막 빙판 위에 돌멩이가 있고 내 캐릭터가 빙판 위에서는 미끄러지며 부딪힐 때 까지 앞으로만 가는... 그렇게 빙판 위를 탈출하는 룰이었던 것 같다.

 

이제 이 문제를 코딩으로 풀어야한다. 어릴 땐 이리저리 막 눌러보면서 탈출했던 것 같은데 문제에서 요구하는 것은 최소한의 이동으로 동굴을 탈출하는 것이다.

 

경로 탐색에 최소한의 이동 횟수. 가장 먼저 떠오른 것은 BFS이다. 위 아래 왼쪽 오른쪽으로 이동한 경우를 체크해가면서 방문한 곳은 더이상 방문하지 않고 해당 작업을 반복한다.

 

여기서 주의해야할 점은 두가지 정도 있는 것 같다.

1. 이동시에 한칸씩 이동하는 것이 아니라 벽에 부딪힐 때 까지 or 장애물에 부딪힐 때 까지 이동시킨다는 점

2. 이미 방문한 곳은 더이상 방문하지 않는다는 점

 

이 두 부분만 체크해가면서 BFS로 코드를 작성하게 되면 쉽게 풀 수 있다.

 

코드

function solution(board) {
    const moves = [[-1, 0], [0, 1], [1, 0], [0, -1]]
    let curPos = []
    
    // 시작지점 위치 찾기 및 string을 배열로 변환
    board = board.map((row, rowIndex) => {
        const rIndex = row.indexOf('R');
        
        if(rIndex !== -1) {
            curPos = [rowIndex, rIndex]
        }
        
        return row.split('');
    })

    let Q = [curPos];
    let count = 0;
    
    while(Q.length) {
        let tempQ = [];
        count++;
        
        while(Q.length) {
            // 이번 큐를 모두 소진시킬 때 까지 반복
            const [x, y] = Q.pop();
            
            for(const [moveX, moveY] of moves) {
                let [curX, curY] = [x, y];
                
                while(1) {
                    // 이동하기로 한 방향 끝까지 이동시키는 로직
                    const nextLocation = board[curX + moveX]?.[curY + moveY];
                    const curLocation = board[curX][curY];
                    
                    if(!nextLocation || nextLocation === 'D') {
                    	// 다음 위치가 배열 바깥이거나 'D'일 경우
                        
                        if(curLocation === 'G') {
                            return count;
                        }
                        
                        if(curLocation !== 'R') {
                            board[curX][curY] = 'R';
                            tempQ.push([curX, curY])
                        }

                        break;
                    } else {
                        [curX, curY] = [curX + moveX, curY + moveY];
                    }
                }
            }
        }
        
        Q = tempQ
    }   
    
    // 도달하지 못했는데 더이상 움직일 수 없는 경우 -1 리턴
    return -1;
}

 

 

설명에 오류가 있거나 궁금하신 부분이 있으면 언제든지 댓글 달아주세요.

공감은 저에게 큰 힘이 됩니다. 읽어주셔서 감사합니다!