[프로그래머스] 등굣길

풀이)

백준 1520 내리막 문제 풀이를 응용해서 풀었다. (dp와 dfs)

다른 점이라면, 최단 경로의 수를 구하는 것이므로 방향을 상하좌우가 아닌 하우만 본다는 것이다.

돌아가는 경로를 아예 차단하는 방법

주의점

m과 n이 어떤 좌표를 뜻하는지 잘봐야한다.

m이 가로고, n이 세로다.

물웅덩이도 {m,n} 좌표로 준다.

코드)

include <string>
#include <vector>
#include<string.h>
using namespace std;
int dp[101][101];
int dy[2] = {1,0};
int dx[2] = {0,1};
#define mod_val 1000000007
int dfs(int y,int x, int m,int n){
    if(y== n &&x == m )return 1;
    if(dp[y][x] == -1){
        dp[y][x] = 0;
        for(int i=0;i<2;i++){
            int ny = y + dy[i];
            int nx = x + dx[i];
            if(ny> 0 && ny <=n && nx>0 && nx<= m){
                if(dp[ny][nx] == -2) continue;
                dp[y][x] += dfs(ny,nx,m,n) % mod_val;
            }
        }
    }
    return dp[y][x];
}
int solution(int m, int n, vector<vector<int>> puddles) {
    int answer = 0;
    memset(dp,-1,sizeof(dp));
    for(int i=0;i<puddles.size();i++){
        dp[puddles[i][1]][puddles[i][0]] = -2;//여기 주의
    }
    dfs(1,1,m,n);
    return dp[1][1] % mod_val;
}