[JS] 등굣길

 

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

프로그래머스

 

 

 

동적계획법 (dp) 를 활용하면 해결할 수 있는 문제이다.

2차원 배열을 둔 후 dp에 이를 저장하면 된다.

 

dp[r][c] = dp[r-1][c] + dp[r][c-1] 

위 점화식을 활용하면 m,n까지 갈 수 있는 경로를 모두 구할 수 있다. 조금까다로운 부분은 2가지가 있다.

 

1. 웅덩이

[일단 웅덩이가 row,col 이 아니라 col,row로 되어있다;; 조심해야함]

웅덩이를 처음에 1로 두고 dp를 순회할때 1을 만난 경우에 이를 0으로 바꿔줌으로써 웅덩이 영역을 지나갈 수 없도록 처리했다.

 

2. 배열의 크기

맨 처음에는 배열의 크기를 m*n으로 두고 첫 행과 첫 열들을 모두 1로 초기화 해주는 방법을 사용했었다. 하지만 이런 방법으로는 1 * n이나 1 * m 의 크기로 조건이 들어오는 경우에 제대로 대응하기가 어렵다.

 

따라서 n+1 * m+1 배열로 만들어서 시작하게 구현하였다.

 

 

 

 

 

function solution(m, n, puddles) {
    const dp = [...Array(n+1)].map(_ => Array(m+1).fill(0))
    
    for (const [c,r] of puddles){
        dp[r][c] = 1
    }
    dp[0][1] = 1
    
    for (let r = 1 ; r <= n ; r++){
        for (let c = 1 ; c <= m ; c++){
            if(dp[r][c]) dp[r][c] = 0
            else dp[r][c] = (dp[r-1][c] + dp[r][c-1]) % 1000000007
        }
    }
    
    return dp[n][m]
}

 

 

끄읏 -!