등굣길

class Solution {
    public int solution(int m, int n, int[][] puddles) {
        int answer = 0;
        int[][] arr = new int[n + 1][m + 1];
        int divNum = 1000000007;
        // 직선 코스일 경우
        if(m == 1 || n == 1){
            if(puddles.length > 0)
                return 0;
            else
                return 1;
        }
        
        // 물에 잠긴 곳 초기화
        for (int i = 0; i < puddles.length; i++) {
            int row = puddles[i][1];
            int col = puddles[i][0];
            arr[row][col] = -1;
        }
 
        boolean flag = false;
        // 왼쪽 웅덩이 체크
        for (int i = 2; i < n + 1; i++) {
            if (arr[i][1] == -1)
                flag = true;
            else if (flag)
                arr[i][1] = 0;
            else
                arr[i][1] = 1;
        }
        // 위쪽 웅덩이 체크
        flag = false;
        for (int i = 2; i < m + 1; i++) {
            if (arr[1][i] == -1)
                flag = true;
            else if (flag)
                arr[1][i] = 0;
            else
                arr[1][i] = 1;
        }
 
        for (int i = 2; i < n + 1; i++) {
            for (int j = 2; j < m + 1; j++) {
                if (arr[i][j] == -1) // 현 위치가 물에 잠겼을 경우
                    continue;
                if (arr[i - 1][j] == -1) // 위쪽이 물에 잠겼을 경우
                    arr[i][j] = arr[i][j - 1];
                else if (arr[i][j - 1] == -1) // 왼쪽이 물에 잠겼을 경우
                    arr[i][j] = arr[i - 1][j];
                else if (arr[i - 1][j] == -1 && arr[i][j - 1] == -1) // 왼쪽, 위쪽이 물에 잠겼을 경우
                    arr[i][j] = 0;
                else
                    arr[i][j] = (arr[i][j - 1] + arr[i - 1][j]) % divNum;
            }
        }
        answer = arr[n][m];
        return answer;
    }
}

동적 계획법을 이용하여 왼쪽, 위쪽으로 오는 경로 값을 모두 더해주었다.

이 때 물에 잠긴 경우를 예외 처리하였다.