📖 문제

계속되는 폭우로 일부 지역이 물에 잠겼습니다. 물에 잠기지 않은 지역을 통해 학교를 가려고 합니다. 집에서 학교까지 가는 길은 m x n 크기의 격자모양으로 나타낼 수 있습니다.

아래 그림은 m = 4, n = 3 인 경우입니다.

가장 왼쪽 위, 즉 집이 있는 곳의 좌표는 (1, 1)로 나타내고 가장 오른쪽 아래, 즉 학교가 있는 곳의 좌표는 (m, n)으로 나타냅니다.

격자의 크기 m, n과 물이 잠긴 지역의 좌표를 담은 2차원 배열 puddles이 매개변수로 주어집니다. 오른쪽과 아래쪽으로만 움직여 집에서 학교까지 갈 수 있는 최단경로의 개수를 1,000,000,007로 나눈 나머지를 return 하도록 solution 함수를 작성해주세요.

✍ 입출력 예

📄 입출력 예 설명

✅ 코드 및 설명

import java.util.*;

class Solution {
    public static int solution(int m, int n, int[][] puddles) {
	    int MOD_VALUE =  1_000_000_007;
        int[][] arr = new int[n][m];
        // 시작점만 1로 채움
        arr[0][0] = 1;

		// 배열의 웅덩이 위치에 -1로 값을 채움
        for(int[] puddle : puddles) {
            int x = puddle[0] -1;
            int y = puddle[1] -1;
            arr[y][x] = -1;
        }

        for(int i=0; i<n; i++) {
            for(int j=0; j<m; j++) {
	            // 웅덩이가 있는 위치는 0으로 값을 변경
                if(arr[i][j] == -1) {
                    arr[i][j] = 0;
                    continue;
                }

				/*  
				* 웅덩이가 없는 위치에는 왼쪽, 위 값을 더해주고,
				* 계속 누적되어 값이 너무 커지는 것을 막기 위해 매번 나머지 값을 구해줌
				*/
                if(i > 0) { arr[i][j] += arr[i-1][j] % MOD_VALUE; }
                if(j > 0) { arr[i][j] += arr[i][j-1] % MOD_VALUE; }
            }
        }

        return arr[n-1][m-1] % MOD_VALUE;
    }
}

문제를 풀때 계속 누적되어 값이 너무 커지는 것을 막기 위해 점화식에 매번 1,000,000,007의 나머지를 구하고 더해주는 작업을 꼭 해줘야 해결할 수 있었습니다.