(프로그래머스) 등굣길

문제 링크

• 프로그래머스

요약

• LeetCode 3418 과 유사한 문제

최종 §

결과

• LeetCode 3418 과 비슷하게 접근하면 된다.

#include <string>
#include <vector>
#include <set>
 
using namespace std;
 
#define MOD (1000000007)
 
int solution(int m, int n, vector<vector<int>> puddles) {
	vector<vector<int>> dp(m, vector<int>(n, 1));
 
    for (auto &p : puddles) {
        dp[p[0] - 1][p[1] - 1] = 0;
    }
 
    dp[0][0] = 1;
 
    for (int x = 0; x < m; x++) {
        for (int y = 0; y < n; y++) {
            if (dp[x][y] == 0) {
                continue;
            } else if (x == 0 && y == 0) {
                continue;
            } else if (x == 0) {
                if (dp[x][y - 1] == 0) {
                    dp[x][y] = 0;
                } else {
                    dp[x][y] = dp[x][y - 1];
                }
            } else if (y == 0) {
                if (dp[x - 1][y] == 0) {
                    dp[x][y] = 0;
                } else {
                    dp[x][y] = dp[x - 1][y];
                }
            } else {
                if (dp[x][y - 1] == 0 && dp[x - 1][y] == 0) {
                	dp[x][y] = 0;
                } else if (dp[x - 1][y] == 0) {
                    dp[x][y] = dp[x][y - 1];
                } else if (dp[x][y - 1] == 0) {
                    dp[x][y] = dp[x - 1][y];
                } else {
                    dp[x][y] = (dp[x - 1][y] + dp[x][y - 1]) % MOD;
                }
            }
        }
    }
 
    return dp[m - 1][n - 1] % MOD;
}