프로그래머스 등굣길 Lv3 / JAVA

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

프로그래머스

 

* 최단거리 값이 아닌 최단거리 갯수를 구하는 문제이다.

* m과 n 을 배열로 계산하기 위해 바꾸어주었다.

 

> 풀이

class Solution {
    public int solution(int m, int n, int[][] puddles) {       
       int answer = 0;

       int[][] dp = new int[n+1][m+1];

       //물 웅덩이
       for(int[] x: puddles) {        	
           dp[x[1]][x[0]] = -1;
       }

       dp[1][1] = 1;
       
       /* 물 웅덩이가 있는 맵
        0 0 0 0 
        0 -1 0 0 
        0 0 0 0
       */

       for(int i = 1; i <= n; i++) {
           for(int j = 1; j <= m; j++) {
               if(dp[i][j] != -1) {

                  if(j > 1 &&  dp[i][j-1] != -1){ // 우측으로 이동
                      dp[i][j] += dp[i][j-1] % 1000000007;

                  }
                  if(i > 1 && dp[i-1][j] != -1) { // 아래로 이동
                      dp[i][j] += dp[i-1][j] % 1000000007;
                  }
               } 
           }    	   
       }

       /* 최단거리가 아닌 (4,3) 최단거리 갯수 
        1 1 1 1 
        1 -1 1 2 
        1 1 2 4        
       */
       
       answer = dp[n][m] % 1000000007;
       return answer;
    }
}