[JS] 수레 움직이기

 

예외처리가 조금 복잡한 BFS문제였다.

 

 

아래 항목들만 생각하면 문제에 조금 쉽게 접근할 수 있다.

 

1. 한턴에 빨간공,파란공은 한번씩 움직인다.

2. 빨간공이나 파란공이 도착했다면 더이상 움직이지 않는다.

3. 두 공은 같은 위치로 움직일 수 없다.

4. 두 공은 서로 교차하며 움직일 수 없다.

 

 

1번에서 특히 빨간공 파란공이 한번에 움직인다는 점에 포커스를 두면 된다.

 

BFS를 통해서 빨간공을 상,하,좌,우로 움직이는 경우마다 파란공또한 움직이면 된다.

 

map의 size가 5*5로 주어지는 이유이다. 총 16가지의 경우의 수들을 한 턴마다 증가시키면서 검사해야하기 때문이다.

 

 

 

function solution(maze) {
    const rLen = maze.length
    const cLen = maze[0].length
    
    const dc = [1,0,-1,0]
    const dr = [0,1,0,-1]
    
    //방문배열 생성
    const redVisited = maze.map(v => Array(cLen).fill(false))
    const blueVisited = maze.map(v => Array(cLen).fill(false))
    
    //맵 정보 저장
    let redCood,blueCood,redDest,blueDest
    for (let i = 0 ; i < rLen ; i++){
        for (let j = 0 ; j < cLen ; j++){
            if(maze[i][j]===1) {
                redCood = [i,j]
                redVisited[i][j] = true
            }
            if(maze[i][j]===2) {
                blueCood= [i,j]
                blueVisited[i][j] = true
            }
            if(maze[i][j]===3) redDest= [i,j]
            if(maze[i][j]===4) blueDest= [i,j]
        }
    }
    
    const isEqualAry = (a,b) => {
        for (let i =0 ; i <a.length ; i++){
            if(a[i]!==b[i]) return false
        }
        return true
    }
    
    const isCanMove = (r,c,visited,otherR,otherC) => {
        if (0<=r&&r<rLen&&0<=c&&c<cLen&&!visited[r][c]&&maze[r][c]!==5&&(otherR!==r||otherC!==c)) return true
        return false
    }
    
    let ret = Infinity
    const dfs = (redCood,blueCood,cnt) => {
            //둘다 도착한 경우
            if(isEqualAry(redCood,redDest) && isEqualAry(blueCood,blueDest)) {
                ret = Math.min(ret,cnt)
                return
            }
            
            if(isEqualAry(redCood,redDest)){ //red만 도착한 경우
                for (let bd = 0 ; bd < 4 ; bd++){
                        const [nBlueR,nBlueC] = [blueCood[0] + dr[bd] , blueCood[1] + dc[bd]]
                        if(isCanMove(nBlueR,nBlueC,blueVisited,...redCood)){
                            blueVisited[nBlueR][nBlueC] = true
                            dfs(redCood,[nBlueR,nBlueC],cnt+1)
                            blueVisited[nBlueR][nBlueC] = false
                        }
                }
            }else if(isEqualAry(blueCood,blueDest)){ //blue만 도착한 경우
                for (let rd = 0 ; rd < 4 ; rd++){
                const [nRedR,nRedC] = [redCood[0] + dr[rd] , redCood[1] + dc[rd]]
                if(isCanMove(nRedR,nRedC,redVisited,...blueCood)){
                    redVisited[nRedR][nRedC] = true
                    dfs([nRedR,nRedC],blueCood,cnt+1)
                    redVisited[nRedR][nRedC] = false
                    }   
                }
            } else { //둘다 도착하지 않음
                for (let rd = 0 ; rd < 4 ; rd++){
                const [nRedR,nRedC] = [redCood[0] + dr[rd] , redCood[1] + dc[rd]]
                if(isCanMove(nRedR,nRedC,redVisited,[-1,-1])){
                    redVisited[nRedR][nRedC] = true
                    for (let bd = 0 ; bd < 4 ; bd++){
                        const [nBlueR,nBlueC] = [blueCood[0] + dr[bd] , blueCood[1] + dc[bd]]
                        if(isCanMove(nBlueR,nBlueC,blueVisited,nRedR,nRedC) &&
                            !(isEqualAry([nBlueR,nBlueC],redCood) && isEqualAry(blueCood,[nRedR,nRedC]) 
                             //서로 뒤바뀌며 움직이는 경우 체크
                             )){
                            blueVisited[nBlueR][nBlueC] = true
                            dfs([nRedR,nRedC],[nBlueR,nBlueC],cnt+1)
                            blueVisited[nBlueR][nBlueC] = false
                        }
                    }
                    redVisited[nRedR][nRedC] = false
                }   
            }
        }
        
            
            
    }
    
    dfs(redCood,blueCood,0)
    
    return ret=== Infinity ? 0 : ret
    
}