[프로그래머스] 등굣길

문제 링크

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

문제 요약

• 좌상단에서 시작하여 물웅덩이를 피해 오른쪽과 아래쪽으로만 움직여 우하단까지 갈 수 있는 최단경로의 개수를 1,000,000,007로 나눈 나머지를 구한다

풀이 흐름

• 최단경로의 개수를 구하라고 했는데, 가로 세로 길이가 정해져 있고 오른쪽과 아래쪽으로만 움직일 수 있으므로 왔던 길을 되돌아 가거나 우회해서 가는 경우가 생길 수 없다. 따라서 최대 최소 길이 신경 쓸 필요 없이 좌상단에서 우하단으로 갈 수 있는 경우의 수만 구하면 된다.
• 현재 위치에서 다음 위치로 가는 방법은 오른쪽으로 이동, 아래쪽으로 이동 뿐 이므로 -> 이전 위치에서 현재 위치로 오는 방법은 왼쪽에서 오는 경우, 위쪽에서 오는 경우 이다.
• 현재 위치까지 오는 방법의 수가 dp[i][j] 라면
  dp[i][j] = dp[i][j-1] + dp[i-1][j]
  -> 최단 경로의 개수를 1,000,000,007로 나눈 나머지를 구해야 하므로
  dp[i][j] = (dp[i][j-1] + dp[i-1][j]) % 1000000007

---

코드

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

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

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

    for(auto p : puddles)
    {
        map[p[1]][p[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 (map[i][j] < 0)
			{
				dp[i][j] = 0;
				continue;
			}

			dp[i][j] = (dp[i][j - 1] + dp[i - 1][j])% 1000000007;
		}
	}

	return dp[n][m];
}