Algorithm, boj, 내리막길(1520)
틀린이유와 풀이
- boolean[][] visitied을 이용해서 일반 dfs로 풀어주면 타임아웃이 발생한다
- dp[i][j] = (i,j)지점에서 끝까지 갈수있는 경로 개수로 지정해서 메모이제이션을 이용할것
- ex) dp[2][3] = 1이라면 2,1->2,2->2,3 에 도착할때 2,3지점에서 끝까지 갈수있는 경로는 이미 1개 있으니까 return dp[2][3]해준다
- 모든 경로의 수를 더해주면 끝.
주의
- 내리막길로 이동하다가 더이상 내리막길이 없어 중간에 멈추는 경우가 생길 수 있는데
- 이 때 dp값은 0이 되어야 할 것입니다. (갈 수있는 경로가 0개이다)
- 그런데 dp 초기값을 0으로 설정한 경우, 가기를 시도한 경로인지, 갈 수가 없는 경우인지 구분 할 수 없어 memoization을 하지 못하고 다시 연산을 하므로 시간이 초과 된다
- 따라서 dp 초기값을 위 경우(0)를 처리할 수 있는 값으로 설정해야 한다. (예: -1)
package org.baekjoon;
import java.util.Scanner;
public class test1520_dp_downhill {
static int m,n;
static int[][] arr,dp;
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
m = sc.nextInt();
n = sc.nextInt();
arr = new int[m][n];
dp = new int[m][n];
for (int i=0; i<m; i++) {
for(int j=0; j<n; j++) {
arr[i][j] = sc.nextInt();
dp[i][j] = -1;
}
}
// 위치 x,y
fun(0, 0);
System.out.println(dp[0][0]);
for (int i=0; i<m; i++) {
for(int j=0; j<n; j++) {
System.out.print(dp[i][j] + " ");
}
System.out.println();
}
}
static int[] nx = {1,-1,0,0};
static int[] ny = {0,0,1,-1};
public static int fun(int x, int y) {
if (x == (m-1) && y == (n-1)) {
return 1;
}
if (dp[x][y] > -1) {
return dp[x][y];
}
int result = 0;
for (int i=0; i<4; i++) {
if(x+nx[i] < 0 || x+nx[i] >= m || y+ny[i] < 0 || y+ny[i] >=n)
continue;
if(arr[x+nx[i]][y+ny[i]] < arr[x][y])
result += fun(x+nx[i], y+ny[i]);
}
return dp[x][y]=result;
}
}
Reference
