[ 프로그래머스 ] 42898 등굣길

📌 Problem

2차원 배열 형태의 도시가 있다. (0, 0)에 집이 있으며 (m - 1, n - 1)에 학교가 있다. m방향과 n방향으로만 움직일 수 있다. 또한 중간에 있는 웅덩이는 지나갈 수 없다. 집에서 학교까지 갈 수 있는 경우의 수를 1,000,000,007으로 나눈 나머지를 반환한다.

📌 Solution

동적 프로그래밍으로 간단하게 해결할 수 있다.

Step 1. 웅덩이 위치 구하기
도시의 전체 도록 크기와 같은 크기의 통과 금기 배열을 만들고 입력값에 따라 접근이 가능한지 아닌지를 판단한다.

Step 2. 1가지 방법 뿐인 곳들을 초기화
(0, 0)에서 우측 혹은 하단으로만 움직여서 갈 수 있는 도로들은 도착 방법이 한 가지이기 때문에 1로 초기화한다. 다만, 중간에 웅덩이가 있으면 이후의 도로들에는 갈 수 없기 때문에 1로 초기화 하지 않는다.

Step 3. DP를 실행한다.
(1, 1)부터 시작하여 (m - 1, n - 1)까지 2중 반복문으로 탐색한다. 특정 위치 (i, j)의 도로로 갈 수 있는 경우의 수는 (i - 1, j) + (i, j - 1)이다. 이 때 나머지 계산을 계속한다.

📌 Code

class Solution {
    public int solution(int M, int N, int[][] puddles) {
        int[][] roads = new int[M][N];
        boolean[][] banned = new boolean[M][N];

        for (int[] puddle : puddles) banned[puddle[0] - 1][puddle[1] - 1] = true;
        for (int m = 1; m < M && !banned[m][0]; m++) roads[m][0] = 1;
        for (int n = 1; n < N && !banned[0][n]; n++) roads[0][n] = 1;

        for (int m = 1; m < M; m++)
            for (int n = 1; n < N; n++)
                if (!banned[m][n])
                    roads[m][n] = (roads[m - 1][n] + roads[m][n - 1]) % 1_000_000_007;

        return roads[M - 1][N - 1];
    }
}