사용한 것
- 2차원 배열의 (1, 1)에서 (m, n)까지 가는 경로의 경우의 수를 구하기 위한 bottom up
풀이 방법
- bottom up으로 경로의 수를 저장할
dp
를 할당한다.
- 물에 잠긴 지역은
dp
에 -1을 넣어준다.
- 1열과 1행으로 가는 방법은 항상 하나 밖에 없으므로 1을 넣는다.
- 이 때 물에 잠긴 지역을 만나면 그 뒤로는 넣어주지 않는다. (갈 수 없으므로)
- bottom up을 시작하여 위에서 오는 경우의 수와 왼쪽에서 오는 경우의 수를 더해서 해당 (i, j)에 넣어준다.
- 해당 좌표가 물 웅덩이인 경우는 패스한다.
- 위, 왼쪽의 좌표가 물 웅덩이면 -1 대신 0을 더해준다.
- 더해서 넣어줄 때 1,000,000,007의 나머지를 넣어준다 (문제 조건)
- (1, 1)에서 (m, n)까지 가는 경로의 경우의 수인
dp[m][n]
을 반환한다.
코드
class Solution {
public int solution(int m, int n, int[][] puddles) {
int[][] dp = new int[m + 1][n + 1];
for (int i = 0; i < puddles.length; i++) {
dp[puddles[i][0]][puddles[i][1]] = -1;
}
for (int i = 2; i <= m; i++) {
if (dp[i][1] == -1) {
break;
}
dp[i][1] = 1;
}
for (int i = 2; i <= n; i++) {
if (dp[1][i] == -1) {
break;
}
dp[1][i] = 1;
}
for (int i = 2; i <= m; i++) {
for (int j = 2; j <= n; j++) {
if (dp[i][j] == -1) {
continue;
}
int up = dp[i - 1][j] == -1 ? 0 : dp[i - 1][j];
int left = dp[i][j - 1] == -1 ? 0 : dp[i][j - 1];
dp[i][j] = (up + left) % 1_000_000_007;
}
}
return dp[m][n];
}
}