(Java) 프로그래머스 - 등굣길

문제를 읽고 DFS / BFS로도 풀 수 있겠다는 생각을 했다.

그런데 문제 유형이 DP로 분류되어 있어서 시간 초과가 나지 않을까 싶어서 

DP로 풀수 있는 방법을 생각해서 해결했다.

---

로직

먼저 m x n인 arr 배열을 만들고 웅덩이를 -1로 초기화한다.

그리고 첫 번째 행과 열이 아니면 이전 행과 열의 값을 더하며 탐색을 진행한다.

최종적으로 마지막 행과 열에는 도달할 수 있는 방법의 개수가 값으로 들어있게 된다.

 

최종 코드

class Solution {
    public int solution(int m, int n, int[][] puddles) {
        int answer = 0;
        // n x m 배열 초기화
        int[][] arr = new int[n][m];
        // 시작점은 1
        arr[0][0] = 1;

        // 웅덩이 배열에서 -1로 설정
        for (int i = 0; i < puddles.length; i++) {
            arr[puddles[i][1] - 1][puddles[i][0] - 1] = -1;
        }

        // dp 탐색
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (arr[i][j] == -1) {
                    arr[i][j] = 0;
                    continue;
                }

                if (i != 0) {
                    arr[i][j] += arr[i - 1][j] % 1000000007;
                }

                if (j != 0) {
                    arr[i][j] += arr[i][j - 1] % 1000000007;
                }
            }
        }

        answer = arr[n - 1][m - 1] % 1000000007;
        return answer;
    }
}