[프로그래머스] 등굣길

https://school.programmers.co.kr/learn/courses/30/lessons/42898

코드

class Solution {
    static public int solution(int m, int n, int[][] puddles) {
        int[][] dp = new int[n + 1][m + 1];
        for (int[] puddle : puddles) {
            dp[puddle[1]][puddle[0]] = -1;
        }

        // 시작점(dp[1][1])을 1로 초기화하기 위해 설정
        dp[0][1] = 1;
        int sum = 0;

        // 현재 위치로 올 수 있는 경로의 개수는 dp 배열의 위와 왼쪽의 값을 더한 값이다.
        // 만약 -1일 경우에는 합 연산에서 제외한다.
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= m; j++) {
                if (dp[i][j] == -1) {
                    continue;
                }

                sum = 0;
                if (dp[i - 1][j] != -1) {
                    sum += dp[i - 1][j];
                }
                if (dp[i][j - 1] != -1) {
                    sum += dp[i][j - 1];
                }

                dp[i][j] = sum % 1000000007;
            }
        }

        return dp[n][m];
    }
}

풀이

좌표상에서 오른쪽과 아래쪽으로만 움직이기 때문에 특정 위치에 도달했을 때의 경로는 항상 최단경로다. 따라서 우리는 학교까지의 모든 경로 개수를 구하면 된다.

dp[i][j]에 도달하는 경로의 개수는 dp[i-1][j] + dp[i][j-1]이다. 만약 둘 중 하나가 -1(물에 잠긴 곳)이라면 덧셈 연산에서 제외한다. 예제를 표로 그려보면 다음과 같을 것이다.

집(1, 1)에서 출발하는 경우의 수는 항상 1개다. (3, 2)에서는 왼쪽 값이 -1이므로 위의 값 1만 더한다. (A + B) % C == (A % B) + (A % C)이므로 표의 값을 갱신할 때마다 모듈로 연산을 수행한다.

주의해야 할 점으로, 물에 잠긴 곳(puddles) 좌표는 2차원 배열이 아니라 (x, y) 좌표 방식으로 제공된다. 처음에 아무 생각없이 dp[puddle[0]][puddle[1]] = -1;로 처리해서 오답이 떠서 한참 헤맸었다.