[ 프로그래머스 ] 등굣길

문제

---

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

풀이

---

최단 경로를 탐색하는 DP 문제로, (1, 1)에서 (m, n)로 이어지는 최소 거리를 구하면서 제시된 위치를 피해야 한다. 따라서 주어진 회피 위치에 음수 값을 지정, 해당 위치를 지나지 않게 한다. 그리고 오른쪽과 아래쪽으로만 움직일 수 있으므로, 왼쪽과 위쪽 값을 메모이제이션하여 (m, n)로 이어지는 최단 경로 경우의 수를 구한다.

#include <string>
#include <vector>

using namespace std;

int dp[101][101] = { 0 };

int solution(int m, int n, vector<vector<int>> puddles)
{
    int answer = 0;

    for (int i = 0; i < puddles.size(); i++)
    {
        dp[puddles[i][1]][puddles[i][0]] = - 1;
    }

    dp[1][1] = 1;

    for (int i = 1; i <= n; i++)
    {
        for (int j = 1; j <= m; j++)
        {
            if (i == 1 && j == 1)
            {
                continue;
            }

            if (dp[i][j] != -1)
            {
                int top = 0;
                int left = 0;

                if (dp[i - 1][j] != -1)
                {
                    top = dp[i - 1][j];
                }

                if (dp[i][j - 1] != -1)
                {
                    left = dp[i][j - 1];
                }

                dp[i][j] = (top + left) % 1000000007;
            }
        }
    }

    answer = dp[n][m];

    return answer;
}