[프로그래머스] 등굣길 - JAVA

문제 링크

문제 정의

• 격자 형태의 지도에서 집 $(1, 1)$에서 학교 $(m, n)$까지 이동하려고 함
• 이때 오른쪽 또는 아래쪽으로만 이동 가능
• 일부 물에 잠긴 칸이 존재하며 물에 잠긴 칸은 이동 불가

목표

물에 잠긴 칸을 피하면서 학교까지 도달하는 "최단 경로의 개수" 구하기

---

접근 방법

경우의 수를 구하는 문제는
가장 먼저 다이나믹 프로그래밍으로 풀 수 있는지를 확인해야 합니다.

2차원의 공간이 주어지고 이 행과 열의 최대는 $100$이고
오른쪽과 아래로만 이동하기 떄문에 순회하면서
$O(M*N)$으로 해결할 수 있습니다.

1. 초기화

outbound를 해결하기 위해
dp의 행은 n+1 열은 m+1로 생성합니다.

int[][] dp = new int[n+1][m+1];

또한 웅덩이를 피해가야 하므로
dp배열에 웅덩이가 있는 좌표에 -1로 초기화 합니다.

for (int[] puddle : puddles) {
	dp[puddle[1]-1][puddle[0]-1] = -1;
}

또한 시작지점인 $(0, 0)$에서 시작하므로 1로 초기화 합니다.

dp[0][0] = 1;

---

2. 상태 전이

현재 위치 $(i, j)$에서:

• 오른쪽 $(i, j+1)$
• 아래 $(i+1, j)$

로 이동하면서 경로를 누적하는 점화식은 아래와 같습니다.

$dp[i][j]→dp[i][j+1],dp[i+1][j]$

다만 물웅덩이인 경우는 건너뜁니다.

---

3. 주의 사항

이 문제는 결과값을 $1,000,000,007$로 나눠야 합니다.
잊지말고 점화식에 추가해야 합니다.

또한 현재 좌표가 웅덩이인 경우는 생략하고
이동할 좌표가 웅덩이인 경우도 생략하도록 구현해야 합니다.

---

코드

import java.util.*;

class Solution {
    static final int DIV = 1000000007;
    public int solution(int m, int n, int[][] puddles) {
        int[][] dp = new int[n+1][m+1];
        
        for (int[] puddle : puddles) {
            dp[puddle[1]-1][puddle[0]-1] = -1;
        }
        
        dp[0][0] = 1;
        
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (dp[i][j] == -1) continue;
                
                if (dp[i][j+1] != -1) {
                    dp[i][j+1] = (dp[i][j+1] + dp[i][j]) % DIV;
                }
                if (dp[i+1][j] != -1) {
                    dp[i+1][j] = (dp[i+1][j] + dp[i][j]) % DIV;
                }
            }
        }
        
        return dp[n-1][m-1];
    }
}