[JS] 경주로 건설

DP와 BFS를 적절히 활용해야 하는 재미있는 문제였다!

 

 

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

프로그래머스

 

 

dp[r][c]  =  r행 c열까지 도달하는데 드는 최소 비용 이라고 두자.

 

BFS로 장애물을 피해가며 모든 경우의수를 탐색하는데, 만약 dp보다 큰 값으로 해당 칸에 도달했다면 그 경우의 수는 생각하지 않아도 괜찮다.

 

단 해당 문제에서는 조금 생각할만한 점이 몇가지 있다.

 

1. BFS에서 비용을 계산할때 직선이면 100 , 커브이면 600원으로 계산을 해야하므로 내가 진행한 방향또한 계산을 해줘야 한다.

2. 시작 지점에서 건너가는 비용은 무조건 100원으로 쳐야하므로 [1][0] , [0][1] 두가지 지점을 시작점으로 넣고 시작해야 한다.

3. 가고자 하는 dp가 더 싸더라도 내가 더 싸게 갈 수 있는 경우가 존재한다.

 

3번이 잘 이해가 안갈 수 있는데 아래 예시를 보자.

 

//dp
[ 0, 100, 200, 300, 400 ]
[ 100, Infinity, Infinity, Infinity, 1000 ]
[ 200, 800, Infinity, 1700, 1100 ]
[ Infinity, 1400, 2000, 2300, Infinity ]
[ Infinity, Infinity, Infinity, 2400, 3000 ]


//board
[ 0, 0, 0, 0, 0 ]
[ 0, 1, 1, 1, 0 ]
[ 0, 0, 1, 0, 0 ]
[ 1, 0, 0, 0, 1 ]
[ 1, 1, 1, 0, 0 ]

 

4행 4번째 줄 2300원이 적혀있는 부분을 보자.

 

왼쪽에서 왔다면 해당 부분은 직진이므로 2100원일 것이다.

하지만 위쪽인 1700원에서 온 경우를 채택하고 있다.

 

그 이유는 해당 dp에 들어갔을때 다음 방향이 직진이냐, 커브냐에 따라서 300원차이는 충분히 뒤집힐 수 있는 값이기 때문이다.

 

따라서 단순하게 dp에 들어있는 최솟값만 생각하는게 아닌, 역전당할수 있는 최대값인 +499원까지 생각해야 한다.

위 방법을 사용하면 굳이 dp안에 방향값까지 넣을필요가 없었다.

 

 

 

좋은 아이디어로 잘 푼 문제같다 ^_^

function solution(board) {
    const dc = [1,0,-1,0]
    const dr = [0,1,0,-1]
    const len = board.length
    
    
    const isCanGo = (r,c) => {
        if(0<=r&&r<len&&0<=c&&c<len&&!board[r][c]) return true
        return false
    }
   const bfs = (sR,sC) => {
       
       const que = []
       let queIdx = 0
       const dp = [...Array(len)].map(_ =>Array(len).fill(Infinity))
       
       //초기화
       dp[sR][sC] = 0
       if(!board[0][1]) {
           dp[0][1] = 100
           que.push([0,1,100,0])
       }
       if(!board[1][0]){
           dp[1][0] = 100
           que.push([1,0,100,1])
       }
       
       while(queIdx<que.length){
           const [r,c,cnt,d] = que[queIdx]
        
         
           if(r===len-1 && c===len-1){
               ret = Math.min(ret,cnt)
               queIdx ++
               continue
           }
           
           for (let k = 0 ; k < 4 ; k++){
               const [nR,nC] = [r + dr[k],c + dc[k]]
               const nCnt = cnt + (d === k ? 100 : 600)
               //500원은 역전당할 수 있다!
               if(isCanGo(nR,nC)&&dp[nR][nC]+500>nCnt){
                   que.push([nR,nC,nCnt,k])
                   dp[nR][nC] = nCnt
               }
           }
           
           queIdx ++
       }
         
           for (let i = 0 ; i < len ; i++){
               console.log(dp[i])
           }
           
      
   }
   
   let ret = Infinity
   bfs(0,0)
    return ret
}