🔗 Problem

https://www.acmicpc.net/problem/13023

👩‍💻 Code

package baekjoon;
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;
import java.util.Arrays;
import java.util.StringTokenizer;

// 내리막 길

public class BJ1520 {
	
	static int m, n;
	static int[] dx = {-1, 0, 1, 0};
	static int[] dy = {0, 1, 0, -1};
	static int[][] map;
	static int[][] dp;
	
	public static void main(String[] args) throws IOException {
		
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		m = Integer.parseInt(st.nextToken());
		n = Integer.parseInt(st.nextToken());
		map = new int[m+1][n+1];
		dp = new int[m+1][n+1];
		
		for(int i = 1; i <= m; i++) {
			st = new StringTokenizer(br.readLine());
			for(int j = 1; j <= n; j++) {
				map[i][j] = Integer.parseInt(st.nextToken());
			}
		}
		
		if(map[1][1] <= map[m][n]) {
			System.out.println(0);
			System.exit(0);
		}
		
		for(int i = 1; i <= m; i++) {
			Arrays.fill(dp[i], -1);
		}
		
		System.out.println(dfs(1, 1));
	}
	
	private static int dfs(int x, int y) {
		
		if(x == m && y == n) return 1;
		if(dp[x][y] != -1) return dp[x][y];
		
		dp[x][y] = 0;
		for(int i = 0; i < 4; i++) {
			
			int xx = x + dx[i];
			int yy = y + dy[i];
			
			if(xx <= 0 || xx > m || yy <= 0 || yy > n) continue;
			if(map[x][y] > map[xx][yy]) {
				dp[x][y] += dfs(xx, yy);
			}
		}
		
		return dp[x][y];
	}
}

📌 Note

아이디어

• 처음에 DP 생각을 못하고 class 만든 후 DFS를 stack으로 구현했다가 메모리초과 발생했다.
• map에 해당 높이만 저장하고 재귀로 풀었는데 DP를 이상하게 구현해서 시간초과 발생 ..
  visited[][]를 두고 방문했던 위치를 지나가게 되면 answer++하는 방식
• 경로에 대한 count를 전체 map에 대해 DP를 사용하는 것이 아니라, 현위치부터 목표위치까지 map을 쪼개서 구한다.
• 현위치 기준 상하좌우 중에서,
  방문하지 않았다면, 해당 위치~목표 위치까지 dfs로 count를 센 후에 dp[][]에 더해준다.
  방문했다면, 그대로 dp[][] 리턴