[JS] 블록 이동하기

 

대놓고 BFS문제이다. 생각할 점은 로봇이 1칸이 아닌 2칸짜리란 점과 회전이 가능하단점이다.

 

https://school.programmers.co.kr/learn/courses/30/lessons/60063#

프로그래머스

 

 

 

일반적인 BFS를 기본으로 구현을 하되 2칸짜리인 점과 4방향 이동 외에 회전이동이 가능하단 점을 생각하자.

 

기본적으로 로봇의 위치를 생각할때 가로와 세로 두가지가 있는데 가로인 경우에는 왼쪽 부분을, 세로인 경우에는 위쪽 부분을 중심으로 생각하기로 했다.

 

우선 회전 기능을 생각하기 위해서 rotate함수를 하나 만들었다. 

 

1. 로봇이 가로로 있다면 위쪽,아래쪽 각 2칸씩의 공간이 비어있는지 확인해야 한다.

2. 로봇이 세로로 있다면 왼쪽,오른쪽 각 2칸씩의 공간이 비어있는지 확인해야 한다.

 

만약 왼쪽이나 오른쪽이 비어있어도 로봇의 회전축이 2개이므로 2개의 결과가 나오게 된다.

 

 

예를 들어 문제에서 제공한 예시에서 rotate(0,0,1)을 넣는다면 [[0,0,0],[0,1,0]] 이 두가지 경우가 나오게 된다.

 

 

마지막으로 생각할 점은 visited배열의 생성이다.

 

단순히 Row,Col만 저장한다면 로봇의 방문여부를 제대로 기록할 수 없다. 같은 [0,0] 이어도 로봇이 가로이거나 세로일 수 있기 때문이다. 따라서 vistied배열을 3차원 배열로 [n][n][2] 로 선언을 해주자.

 

함수들에서 계속 isRow 변수를 사용하고 있으므로 이에 연결되기 편하게 vistied안쪽의 첫번째를 세로, 두번째를 가로라고 생각하고 저장한 후 BFS를 적용해서 풀었다.

 

 

function solution(board) {
    const len = board.length
    const dc = [1,0,-1,0]
    const dr = [0,1,0,-1]
    
    //가로 -> 왼쪽이 기준
    //세로 -> 위가 기준
    //사방향 조회순서는 우->하->좌->상
   
    //갈수있는지 조회
    const isCanGo = (r,c) =>{
       if (0<=r&&r<len&&0<=c&&c<len&&!board[r][c]) return true
        return false
    }
    //회전시키고 좌표를 반환
    const rotate = (r,c,isRow) => {
       const dr = isRow ? [[1,1],[-1,-1]]: [[0,1],[0,1]]
       const dc = isRow ? [[0,1],[0,1]] : [[1,1],[-1,-1]]
       const nxDirection = +!isRow
       
       const sR = isRow ? [[0,0],[-1,-1]] : [[0,1],[0,1]]
       const sC = isRow ? [[0,1],[0,1]] : [[0,0],[-1,-1]]
       
       const ret = []
       outer : for(let i = 0 ; i < 2 ; i ++){
           for (let j = 0 ; j < 2 ; j++){
               const nR = r + dr[i][j] 
               const nC = c + dc[i][j]
               if(!isCanGo(nR,nC)) continue outer
           }
           
           for (let j = 0 ;j<2;j++){
               const retR = r + sR[i][j]
               const retC = c + sC[i][j]
               ret.push([retR,retC,nxDirection])
           }
        }
        return ret
    }
    
    //첫번째는 세로 , 두번째는 가로의 방문여부
    const visited = [...Array(len)].map(_=>[...Array(len)].map(_=>[0,0]))
    
    const que = [[0,0,1,0]]
    let queIdx= 0
    let ret = Infinity
    while(queIdx < que.length){
        const [r,c,isRow,cnt] = que[queIdx]
        //로봇 나머지의 좌표
        const otherR = isRow ? r : r+1
        const otherC = isRow ? c+1 : c
        
        if(visited[r][c][isRow]) {
            queIdx++
            continue
        }
        visited[r][c][isRow] = true
        // 도착했다면 정보 갱신
        if(otherR===len-1&&otherC===len-1){
            ret = Math.min(ret,cnt)
        }
        //4방향 이동
        for (let d = 0 ; d < 4 ; d++){
            const [nR,nC] = [r+dr[d],c+dc[d]]
            const [nOtherR,nOtherC] = [otherR+dr[d],otherC+dc[d]]
            if(isCanGo(nR,nC)&&isCanGo(nOtherR,nOtherC)){
                que.push([nR,nC,isRow,cnt+1])
            }
        }
        //회전 이동
        for (const [nR,nC,nIsRow] of rotate(r,c,isRow)){
            que.push([nR,nC,nIsRow,cnt+1])
        }
        
        queIdx++
    }
    return ret
}