[프로그래머스 42898] 등굣길 C++

문제

프로그래머스 42898 등굣길 C++

코딩테스트 연습 - 등굣길

풀이

해당 좌표가 웅덩이인지 저장하는 water배열을 선언하고, 웅덩이 좌표를 넣어줍니다.

그 이후에는 일반적인 길찾기 처럼 DP를 이용하되, 웅덩이일 경우에는 경로를 계산하지 않고 넘어갑니다.

소스 코드

#include <string>
#include <vector>
using namespace std;
bool water[101][101];
int dp[101][101];
 
int mod = 1000000007;
int solution(int m, int n, vector<vector<int>> v) {
    int answer = 0;
    // 웅덩이
    for (int i = 0; i < v.size(); i++) {
        int x = v[i][0];
        int y = v[i][1];
        water[y][x] = true;
    }
    dp[1][1] = 1;
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            // 웅덩이면 pass
            if (water[i][j]) {
                continue;
            }
            // 위쪽에서 오는 루트
            if (i - 1 >= 1) {
                dp[i][j] += dp[i - 1][j];
            }
            // 왼쪽에서 오는 루트
            if (j - 1 >= 1) {
                dp[i][j] += dp[i][j - 1];
            }
            dp[i][j] %= mod;
        }
    }
    answer = dp[n][m];
    return answer;
}