다이나믹 프로그래밍이란?
특정 범위까지의 값을 구하기 위해서 그것과 다른 범위까지의 값을 이용하여 효율적으로 값을 구하는 알고리즘 설계 기법이다.
최단경로 문제도 기존 경로 값을 이용하여 쉽게 구할 수 있다.
예제의 기본 테스트케이스를 준비했다.
아래의 지도에 경로의 수를 기록하면 된다.
1. 초기화
2. 경로 계산
등굣길은 오른쪽과 아래 방향으로만 갈 수 있으므로
이 길을 지나갈 수 있는 경우의 수 = 위쪽 길의 경우의 수 + 왼쪽 길의 경우의 수
첫칸(1,1)은 생략하고 왼쪽부터 아래로 차례대로 왼쪽과 위쪽의 값을 더해준다.
웅덩이가 나오면 0으로 설정해주고 더한다.
첫번째 열과 첫번재 행의 계산을 편하게 하기 위해 '2.초기화' 과정에서 깍두기 줄을 추가 해줬다.
3. 정답은 4!!
public int solution(int m, int n, int[][] puddles) {
//배열 생성 및 초기화
int[][] route = new int[m+1][n+1];
route[1][1] = 1;
/* 2. 웅덩이 -1 으로 표시 */
for(int[] p : puddles) {
int i = p[0];
int j = p[1];
route[i][j] = -1;
}
/* 3. 경우의 수 계산 */
for(int i=1 ; i <= m ; i++) {
for(int j=1 ; j <= n ; j++) {
if(i == 1 && j == 1) continue; //첫칸은 생략
if(route[i][j] < 0) {//웅덩이
route[i][j] = 0;
continue;
}
route[i][j] = (route[i][j-1] % 1000000007) + (route[i-1][j] % 1000000007);
}
}
return route[m][n] % 1000000007;
}