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

문제

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

---

풀이

(i, j) 위치로 이동할 수 있는지 dp와 웅덩이 좌표를 사용해서 경우를 더한다.

dp[i][j] = (i,j) 위치까지 최단경로로 올 수 있는 경우의 수  (경로, 즉 누적합이 아님)

- 오른쪽으로 이동 (현재 위치의 왼쪽 dp 더하기)

- 아래로 이동 (현재 위치의 위쪽 dp 더하기)

 

주어진 예시에 대한 dp 값을 표로 표현하면 아래와 같다.

dp[2][3]은 왼쪽인 dp[2][2], 위쪽인 dp[1][3]에서부터 올 수 있으므로 그 두 경우의 수를 더한 값인 4가 된다. 

이전 위치가 웅덩이이거나, 이동하려는 위치가 웅덩이면 제외한다. 

1	1	1	1
1	0	1	2
1	1	2	4

 

#include <bits/stdc++.h>
using namespace std;
const int MOD = 1000000007;
int solution(int m, int n, vector<vector<int>> puddles) {
    int answer = 0;
    vector<vector<int>> dp(n, vector<int> (m, 0));
    
    // 웅덩이 위치 저장
    for(auto p: puddles){
        dp[p[1]-1][p[0]-1] = -1;
    }

    // 초기 시작
    dp[0][0] = 1;
    
    for(int i=0; i<n; i++){
        for(int j=0; j<m; j++){
            // 웅덩이라면 제외
            if(dp[i][j]== -1){
                continue;
            }
            // 아래
            if(i>=1 && dp[i-1][j]!=-1){
                dp[i][j] += dp[i-1][j];
            }
            // 오른쪽 
            if(j>=1&& dp[i][j-1]!=-1){
                dp[i][j] += dp[i][j-1];
            }
            dp[i][j] %= MOD;
        }
    }
    answer = dp[n-1][m-1];
    return answer;
}