[프로그래머스] 42898 등굣길

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

프로그래머스

 

 

이 문제는 (1, 1) 에서 (n, m) 까지  '최단거리'의 수를 찾는 문제입니다.

시작점과 끝점이 정해져있기 때문에 최단거리를 구하기 위해서는 오른쪽/아래로 가는 길만 고려하면 되겠습니다.

또한, 이전의 횟수가 현재의 횟수에 영향을 미치기 때문에 다이나믹 프로그래밍이라고 할 수 있습니다.

재귀로도 풀 수 있고, 배열을 이용해서 풀 수도 있습니다.

 

+) 질문 검색에서는 테스트케이스가

0 0 0 0 0
1  1  1  1  0
0 0 0 0 0 
0 1  1  1  1
0 0 0 0 0 

이러한 경우를 고려하지 않은 것 같다는 의견이 제시되어 있습니다. 제 코드도 저런 경우에는 0을 출력합니다. ㅠㅠ 

근데 다른 피드백도 없고 비슷한 질문검색이 올라오는데도 계속 방치해두고 있는 이유는 아마도 DP만을 고려한 문제기 때문이 아닐까 싶습니다. 정확히는 모르겠지만! 

 

class Solution {
    public int solution(int m, int n, int[][] puddles) {
        
        // init
        int MOD = 1000000007; 
        int[][] dp = new int[n + 1][m + 1]; 
        int[][] map = new int[n + 1][m + 1]; 
        for (int[] puddle : puddles) {
            map[puddle[1]][puddle[0]] = -1; 
        }
        
        dp[1][0] = 1; 
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= m; j++) {
                if (map[i][j] == -1) dp[i][j] = 0; 
                else {
                    dp[i][j] = (dp[i - 1][j] % MOD + dp[i][j - 1] % MOD) % MOD; 
                }
            }
        }
        
        return dp[n][m];
    }
}