[문제 이름 : 등굣길 (프로그래머스 42898, Lv 3)]
문제 url : https://school.programmers.co.kr/learn/courses/30/lessons/42898
내가 작성한 코드는 아래와 같다.
class Solution {
public int solution(int m, int n, int[][] puddles) {
int[][] dp = new int[n][m];
dp[0][0] = 1;
// 물에 잠긴 지역 -1 설정
for(int[] puddle : puddles) {
dp[puddle[1] - 1][puddle[0] - 1] = -1;
}
for(int i=0; i<n; i++) {
for(int j=0; j<m; j++) {
// 물에 잠긴 지역인 경우
if(dp[i][j] == -1) {
dp[i][j] = 0;
continue;
}
// 위쪽에서 값 더함
if(i > 0) {
dp[i][j] += dp[i-1][j];
}
// 왼쪽에서 값 더함
if(j > 0) {
dp[i][j] += dp[i][j-1];
}
dp[i][j] %= 1000000007;
}
}
return dp[n-1][m-1];
}
}
[풀이 과정]
1. 처음 출발할 때를 1로 초기화해주고, puddles에서 물에 잠긴 지역의 x,y좌표를 알 수 있으므로 해당하는 지점을 -1로 초기화 해준다.
2. 오른쪽, 아래 방향으로만 갈 수 있으므로, 이를 다시 생각해보면 왼쪽, 위쪽 값에서 더해질 때만 해당 x,y좌표의 값으로 갱신해주면 된다.
3. dp[i][j]는 (i, j) 위치까지 도달할 수 있는 경로의 수를 저장한다.
4. 문제가 (1,1)에서 시작하므로, dp[n-1][m-1]로 리턴해주었다.
풀이 시간 : 35분