[JS] 리코쳇 로봇

que와 bfs를 활용해서 풀어보았다. que를 활용하긴 했는데 JS에서는 큐 자료구조를 라이브러리로 제공하지는 않아 직접구현해야 하는데 배열 범위가 크지 않아 그냥 배열을 활용해서 풀었다. 

 

 

풀이 방법을 순서에 따라 설명해보겠다.

 

1. 동서남북 방향으로 움직이는것을 구현할 수 있게 도와주는 dx,dy값 생성

2. 배열을 2차원 배열로 만들어줌 (지금 생각하면 원본배열을 수정하는것이 아니라, 굳이 상관 없었을 듯 하다)

3. 로봇의 시작 좌표 찾기

4. 찾을 수 없는경우 그만 찾아야 하므로, 방문한 좌표를 저장할 dp배열을 하나 생성

5. 큐에 로봇의 좌표와 몇번 움직였는지 저장할 cnt값을 넣어서 이를 빼면서 확인

 

[x,y,cnt] <== 이런 형식으로 큐에 쌓이게 되고, 중복을 감지해서 큐에 더 넣지 않기 때문에 전체 경우의 수를 다 파악하면 탐색이 끝나게 된다.

 

6. 미끄러짐을 while문으로 구현해서 장애물을 만나지 않으면 갔다고 생각

7. 동작 수행중 'G'를 만나면 게임종료

8. 큐가 비어질때까지 'G'가 안나오면 -1을 리턴

 

 

 

 

보드에서 nx,ny좌표로 갈수 있는곳인지 아닌지 판단하는 조건문이 너무 지저분해서 isCanGo 함수를 하나 만들어서 가독성을 높여 보았다.

 

 

 

\

 

//갈수 있는곳인지 아닌지 확인해주는 함수
const isCanGo = (x,y,ary) => 
    0<=x && x<ary[0].length && 0<= y && y < ary.length && ary[y][x]!=='D'

function solution(board) {
    const dx = [1,0,-1,0]
    const dy = [0,1,0,-1]
    
    //boardList 2차원 배열 만들기
    const boardList = board.map(el => el.split(""));
    //로봇의 시작 좌표 찾기
    let R;
    for (let i = 0 ; i< board.length ; i++){
        for (let j =0; j<board[0].length ; j++){
            if(boardList[i][j]==='R') R = [j,i,0]
        }
    }
    
    //방문했던 곳인지 확인할 배열
    const dp = [...new Array(board.length)].map((_) => [...new Array(board[0].length)].fill(false))
    
    const que = [R]
    while(que.length) {
        const [x,y,cnt] = que.shift()
        for (let i=0 ; i<4;i++){
            let nx = x 
            let ny = y
            
            while(isCanGo(nx,ny,boardList)){
                const tmpX = nx + dx[i]
                const tmpY = ny + dy[i]
                if (isCanGo(tmpX,tmpY,boardList)) [nx,ny] = [tmpX,tmpY] 
                else break
            }
            
            if(isCanGo(nx,ny,boardList)){
                if (boardList[ny][nx]==='G') return cnt+1
                if (!dp[ny][nx]) {
                    que.push([nx,ny,cnt+1])
                    dp[ny][nx] = true
                }
                
            }
           
        }
    }
    
    return -1;
}