사용한 것
- 시작 지점에서 목표 지점까지 내리막길만 사용하여 도달 가능한 경우의 수를 구하기 위한 top-down
풀이 방법
- 현재 좌표를 이미 방문한 경우
- 현재 좌표를 방문하지 않은 경우
visited
true
- 현재 좌표에서 동, 서, 남, 북으로 도달 가능하고 오르막길이면 해당 경우의 수를 재귀호출하여 모두 더해줌
memo
에 넣고 return
코드
public class Main {
private static final int[] DX = {-1, 0, 1, 0};
private static final int[] DY = {0, 1, 0, -1};
private static int n;
private static int m;
private static int[][] map;
private static boolean[][] visited;
private static int[][] memo;
public static void main(String[] args) throws IOException {
init();
System.out.println(findNumOfPaths(n - 1, m - 1));
}
private static void init() throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
n = Integer.parseInt(st.nextToken());
m = Integer.parseInt(st.nextToken());
map = new int[n][m];
memo = new int[n][m];
visited = new boolean[n][m];
memo[0][0] = 1;
visited[0][0] = true;
for (int i = 0; i < n; i++) {
st = new StringTokenizer(br.readLine());
for (int j = 0; j < m; j++) {
map[i][j] = Integer.parseInt(st.nextToken());
}
}
}
private static int findNumOfPaths(int x, int y) {
if (visited[x][y]) {
return memo[x][y];
}
visited[x][y] = true;
int numOfPaths = 0;
for (int i = 0; i < 4; i++) {
int nx = x + DX[i];
int ny = y + DY[i];
if (isOOB(nx, ny) || map[nx][ny] <= map[x][y]) {
continue;
}
numOfPaths += findNumOfPaths(nx, ny);
}
return memo[x][y] = numOfPaths;
}
private static boolean isOOB(int x, int y) {
return x < 0 || x >= n || y < 0 || y >= m;
}
}