백준 1520 내리막 길

DP와 DFS를 사용하면 풀 수 있다는걸 알았지만 너무 오랜만에 봐서 코드 구현이 헷갈렸던 문제.

단순 DFS 완전탐색으로 하게 되면 시간초과가 난다.
DP를 활용하여 이전에 갔던 곳을 메모이제이션을 통해 빠르게 값을 누적하는 것이 핵심.

처음 dp를 -1로 초기화해야하는데, 그냥 0으로 초기화하게 되면 0인 경우(갈 수 없는 길)도 다시 검색하는 것이라 시간 초과가 난다.

바텀업 방식의 dp 문제를 잘 정리해야겠다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Boj1520 {
	static int n, m;
	static int[][] map;
	static int[][] dp;

	static int[] dx = { 0, 1, -1, 0 };
	static int[] dy = { 1, 0, 0, -1 };

	static int dfs(int x, int y) {
		if(y == n-1 && x== m-1 ) {
			return 1;
		}
		
		if(dp[y][x] != -1) {
			return dp[y][x];
		}
		
		dp[y][x]=0;
		for (int i = 0; i < 4; i++) {
			int nx = dx[i] + x;
			int ny = dy[i] + y;
			if (nx >= 0 && ny >= 0 && nx < m && ny < n) {
				if(map[y][x] > map[ny][nx]) {
					dp[y][x] += dfs(nx,ny);
				}
			}
		}
		return dp[y][x];
	}

	public static void main(String[] args) throws IOException {
		// TODO Auto-generated method stub
		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];
		dp = new int[n][m];
		
		
		for (int y = 0; y < n; y++) {
			st = new StringTokenizer(br.readLine());
			for (int x = 0; x < m; x++) {
				map[y][x] = Integer.parseInt(st.nextToken());
				dp[y][x]=-1;
			}
		}

		System.out.println(dfs(0,0));
	}

}