프로그래머스 - 등굣길

프로그래머스 - 등굣길

위 그림과 같이 (0, 0)에서 (n, m)까지 갈 수 있는 모든 경우의 수를 구하면 되는 문제이다.
중간중간 웅덩이가 있기 때문에 해당 부분을 지나는 경우는 제외해야 한다.
움직임은 우측과 하단으로만 할 수 있기 때문에 (i, j)에 도달할 수 있는 경우의 수는 (i-1, j), (i, j-1)의 경우의 수를 더하면 된다. 물론 중간중간 웅덩이도 체크해줘야 한다.
dp식은 아래와 같다.

dp[i][j] = dp[i][j] == "웅덩이" ? 0 : (dp[i - 1][j] + dp[i][j - 1]);

코드는 다음과 같다.

#include <string>
#include <vector>

using namespace std;

int solution(int m, int n, vector<vector<int>> puddles) {
    int answer = 0;
    vector<vector<int>> dp(n, vector<int>(m, 0));
    
    for(auto it : puddles) 
        dp[it[1] - 1][it[0] - 1] = -1;
    
    dp[0][0] = 1;
    for(int j=1;j<m;j++) {
        if(dp[0][j] == -1) {
            for(int k=j;k<m;k++) 
                dp[0][k] = 0;
            break;
        }
        dp[0][j] = 1;
    }
    for(int i=1;i<n;i++) {
        if(dp[i][0] == -1) {
            for(int k=i;k<n;k++) 
                dp[k][0] = 0;
            break;
        }
        dp[i][0] = 1;
    }
    
    for(int i=1;i<n;i++) 
        for(int j=1;j<m;j++) {
            dp[i][j] = dp[i][j] == -1 ? 0 : (dp[i - 1][j] + dp[i][j - 1]);
            dp[i][j] %= 1000000007;
        }
        
    answer = dp[n - 1][m - 1];
    
    return answer;
}