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

문제 출처 - Programmers

문제는 여기

코딩테스트 연습 - 등굣길

---

[풀이]

1. 웅덩이가 있는 곳을 -1로 초기화를 해준다.

2. 시작 위치는 무조건 1번에 갈 수 있으므로 1을 준다.

3. 배열에서 웅덩이가 있는 위치라면 0으로 값을 준다.

4. 맨 위와 맨 왼쪽의 경우를 제외하고는 이전의 값을 더해준다.

5. 3. ~ 4. 를 반복한다.

6. 마지막의 값을 결과로 출력한다.

[접근]

1. 어릴 적 풀던 수학 문제처럼 해결하면 되겠다고 생각하였고 아래의 방법으로 풀었다.

[코드]

class Solution {
    static int dev = 1000000007;
    
    public int solution(int m, int n, int[][] puddles) {
        int[][] dp = new int[m][n];

        // 웅덩이가 있는 곳이라면 -1로 초기화해준다.
        for (int i = 0; i < puddles.length; i++) {
            dp[puddles[i][0] - 1][puddles[i][1] - 1] = -1;
        }

        // 시작 위치는 무조건 1번
        dp[0][0] = 1;

        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                // 웅덩이면 0으로 바꾸고 continue
                if (dp[i][j] == -1) {
                    dp[i][j] = 0;
                    continue;
                }

                // 맨 위와 맨 왼쪽의 경우는 웅덩이가 없는 이상 1이므로
                // 해당하는 경우를 제외하고는 합을 구한다
                if (i != 0)
                    dp[i][j] += dp[i - 1][j] % dev; 
                if (j != 0)
                    dp[i][j] += dp[i][j - 1] % dev;
            }
        }

        return dp[m - 1][n - 1] % dev;
    }
}