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

등굣길

전형적인 DP 문제입니다. 어렵진 않은데 DP말고 다른 방식으로 풀면 효율성 테스트에서 시간초과가 나와 level 3 에 선정된것같습니다.

집에서 오른쪽 아래로만 움직여 학교까지 가는 최단 거리를 구해야합니다. (중간에 장애물이 존재합니다.)
DP 문제는 규칙을 찾고 점화식을 세우는것이 가장 중요합니다. 규칙을 찾기 위해 종이에 써가면서 풀어보시는걸 추천합니다~~~

2차원 배열을 만들어 장애물은 -1 출발지점은 1로 설정해둡니다.장애물 -1을 만나면 continue를 통해 장애물로 이동하지 않습니다.
오른쪽으로 가는 경우와 아래로 가는 경우 2가지가 있고 반대로 생각해보면 해당 위치의 값은 위에 또는 왼쪽값을 통해 결정됩니다.
이러한 규칙으로 점화식은 각각
map[i][j] += map[i - 1][j] % mod; // 위쪽
map[i][j] += map[i][j - 1] % mod; // 왼쪽
입니다.

class Solution {
    public int solution(int m, int n, int[][] puddles) {
        int mod = 1000000007;
        
        int[][] map = new int[n + 1][m + 1];
        for(int i = 0; i < puddles.length; i++) {
            map[puddles[i][1]][puddles[i][0]] = -1; 
        }
        
        map[1][1] = 1;
        for(int i = 1; i < n + 1; i++) {
            for(int j = 1; j < m + 1; j++) {
                if(map[i][j] == -1) continue;
                if(map[i - 1][j] > 0) map[i][j] += map[i - 1][j] % mod;
                if(map[i][j - 1] > 0) map[i][j] += map[i][j - 1] % mod;
            }
        }
        return map[n][m] % mod;
    }
}