프로그래머스 - 등굣길

 이 문제는 다이나믹 프로그래밍으로 푸는 문제이다. 처음에는 (1,1) 부터 (m,n) 까지 가는 최단경로라는 말만 보고 bfs를 떠올려 풀었지만, 이 문제는 최단경로의 개수를 묻는 문제였다. 핵심은 오른쪽과 아래로만 갈 수 없다는 것인데, 이는 (m,n)까지 도달만 하면 무조건 최단경로가 되는 것이다. (1,1)에서 (m,n)으로 가는데 오른쪽과 아래밖에 못간다면 결국 오른쪽으로 m번, 아래로 n번 가야 최단경로이기 때문이다. 이 문제에서 주의할 점은 y좌표와 x좌표가 반대로 되어있다는 것이다. 

 

#include <string>
#include <vector>
#include <queue>
#include <utility>

using namespace std;

int matrix[101][101];
int dp[101][101];

int dy[] = {0, 1};
int dx[] = {1, 0};

int maxM;
int maxN;

bool inRange(int y, int x)
{
    if (y >= 1 && y <= maxM && x >= 1 && x <= maxN)
    {
        return true;
    }
    return false;
}

int func(int y, int x)
{   
    if (matrix[y][x] == 1)
    {
        return 0;
    }
    
    if (y == maxM && x == maxN)
    {
        return 1;
    }
    
    if (dp[y][x] != -1)
    {
        return dp[y][x];   
    }
    
    int result = 0;
    for (int i = 0; i < 2; i++)
    {
        int nextY = y + dy[i];
        int nextX = x + dx[i];
        
        if (inRange(nextY, nextX))
        {
            result += func(nextY, nextX);
            result %= 1000000007;
        }
    }
    
    return dp[y][x] = result;
}

int solution(int m, int n, vector<vector<int>> puddles) {
    int answer = 0;
    
    maxM = n;
    maxN = m;
    
    for (int i =0; i < 101; i++)
    {
        for (int j = 0; j < 101; j++)
        {
            dp[i][j] = -1;
        }
    }
    
    for (auto p : puddles)
    {
        matrix[p[1]][p[0]] = 1;
    }
    
    answer = func(1, 1);
    answer %= 1000000007;
    
    return answer;
}