[JAVA/프로그래머스] 동적계획법(Dynamic Programming)_등굣길

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
import java.util.*;
/**
 *
 * @author HEESOO
 *
 */
 class Solution {
    public int solution(int m, int n, int[][] puddles) {
        int answer = 0;
        int[][] route=new int[n][m];
        for(int[] row:puddles){//웅덩이 설정
            route[row[1]-1][row[0]-1]=-1;
        }
        route[0][0]=1;//시작값 초기화
        for(int i=0;i<n;i++){
            for(int j=0;j<m;j++){
                if(route[i][j]==-1){//웅덩이는 0으로 변경
                    route[i][j]=0;
                }
                else{//웅덩이가 아니라면
                    if(i-1>=0){//왼쪽 값을 가져올 수 있다면
                        route[i][j]+=route[i-1][j]%1000000007;
                    }
                    if(j-1>=0){//위 값을 가져올 수 있다면
                        route[i][j]+=route[i][j-1]%1000000007;
                    }
                }
                if(i==n-1&&j==m-1){//목적지에 도착했다면
                    answer=route[i][j]%1000000007;
                }
            }
        }
        return answer;
    }
}