1. 문제에 대하여 📦
배열에서 (1,1) 짜리에서 (n,m)짜리 공간으로 이동한다. 이떄 웅덩이가 있는 공간은 갈 수 없을 때, (1,1)에서 (n,m) 까지 가는 경우의 수를 모두 구하라
2. 코드가 나오기까지 🛠️
KEY WORD: DP웅덩이가 없는 기본적인 상황을 생각해보면, 임의의 좌표 (r,c)로 갈 수 있는 경우의 수는 (r-1,c)로 오는 경우의 수와 (r,c-1)로 오는 경우의 수를 더한 값이다.
$$
dp(r,c) = dp(r-1,c) + dp(r,c-1)
$$
$$
dp(r,c) = dp(r-1,c) + dp(r,c-1)
$$
웅덩이가 있는 좌표는 사용하지 못하므로, 해당 좌표는 넘어가거나, 웅덩이 좌표가 현 좌표의 왼쪽이나 위일 경우 더하지 않는 식으로 넘어가면 된다.
(1) 시간복잡도 분석 ⏳
2차원 배열을 한 번 훑는 것이므로 시간복잡도는 다음과 같다.
$$ O(n \times m)$$
$$ O(n \times m)$$
3. 코드 🌐
(1) SUDO CODE 💬
// 생략
(2) JAVA CODE ☕
import java.util.*; class Solution { static int [][] dp; public int solution(int m, int n, int[][] puddles) { int answer = 0; dp = new int [n][m]; if(puddles[0].length > 0){ for(int i =0; i < puddles.length; i++){ dp[puddles[i][1]-1][puddles[i][0]-1] = -999; } } for(int i = 0; i < n; i++){ if(dp[i][0] == -999) break; dp[i][0] = 1; } for(int j = 0; j < m; j++){ if(dp[0][j] == - 999) break; dp[0][j] = 1; } for(int i = 1; i < n; i++){ for(int j = 1; j < m; j++){ if(dp[i][j] == -999) continue; int top = (dp[i-1][j] == -999)? 0: dp[i-1][j]; int left = (dp[i][j-1] == -999)? 0 : dp[i][j-1]; dp[i][j] = (top+left)%1_000_000_007; } } // for(int [] row : dp){ // System.out.println(Arrays.toString(row)); // } answer = dp[n-1][m-1]; return answer; } }
4. 트러블 슈팅 or 배운 점📝
- 문제에서 배열 시작이 0,0 이 아니라 1,1이다. 이거 조정 해줘야 한다.
- 문제에서 배열의 좌표나 배열 자체를 줄떄 행,열이 아니라 열 행으로 준다.
