[프로그래머스] 등굣길 [cpp]

문제 : https://school.programmers.co.kr/learn/courses/30/lessons/42898
알고리즘 : 동적 계획법

핵심

역시나 위치 관리를 잘 해야함.
dp = 이동할 곳 계산 vector리스트
puddles_map = 물웅덩이 위치
dp에서 가로 기준으로 시작하여 첫째줄은 전부다 1로 처리하고
세로 기준도 첫째줄은 1로 처리하는데 두번째 줄 부터는 위와 왼쪽에서 올 수 있는 경우의 수를 생각하여함.
따라서 i, j가 1이상일 경우 왼쪽과 위의 값을 더해야함.

#include <iostream>
#include <vector>
using namespace std;

int solution(int m, int n, vector<vector<int>> puddles) {
    const int MOD = 1000000007;
    // 세로, 가로 0으로 초기화 dp 계산식
    // n, m 1씩 더하는 이유는 puddles 2, 2로 0부터 인덱스 시작아님
    vector<vector<int>> dp(n + 1, vector<int>(m + 1, 0));
    // puddle 위치
    vector<vector<bool>> puddles_map(n + 1, vector<bool>(m + 1, false));

    for (const auto &puddle : puddles) {
        // 전제조건의 웅덩이를 웅덩이 맵에 추가
        puddles_map[puddle[1]][puddle[0]] = true;
    }

    // 시작 지점 1부터 시작
    dp[1][1] = 1;

    // vector가로, 세로 1씩 추가하여 시작하기 때문
    // 가로 부터 채우고 세로 넘어가야하기 때문에 첫 for는 세로
    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= m; ++j) {
            // i = 세로, j = 가로가 물웅덩이면 패스
            if (puddles_map[i][j] == true) {
                dp[i][j] = 0;
                continue;
            }

            // 물웅덩이가 첫번째 이동라인 지났을 경우 위쪽, 왼쪽 더한 값이 현재 위치
            if (i > 1) {
                // 첫째 라인이 아니라면 왼쪽 값을 더하고 MOD로 최단경로 나눔
                dp[i][j] += dp[i - 1][j] % MOD;
            }
            if (j > 1) {
                // 첫째 라인이 아니라면 위쪽 값을 더하고 MOD로 최단경로 나눔
                dp[i][j] += dp[i][j - 1] % MOD;
            }

            dp[i][j] %= MOD;
        }
    }

    return dp[n][m];
}