[Java/자바 백준 1520] 내리막 길

풀이

DFS + DP 문제입니다

처음에 DFS로만 풀었는데 메모리 초과가 발생했습니다.

 

이를 보완하기 위해 DP 메모이제이션 방법을 추가했습니다.

 

나보다 더 낮은 경로일 때 탐색을 계속해서 진행했으며,

목적지까지 도착하면 dp +1 시켜주었습니다.

 

DFS방식이기 때문에 dp가 -1 이 아닌 경우는 이미 끝까지 탐색한 경로이기 때문에

해당하는 dp를 바로 return 시켜주었습니다. 

import java.io.*;
import java.util.*;
// dfs + dp 문제 
public class Main{
	static int N, M;
	static int[][] map;
	static int[][] dp;
	static int[] dx = {-1,0,1,0};
	static int[] dy = {0,-1,0,1};
	public static void main(String[] args) throws Exception{
		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 i = 0 ; i < N ; i ++) {
			st = new StringTokenizer(br.readLine() , " ");
			for(int j = 0 ; j < M ; j++) {
				map[i][j] = Integer.parseInt(st.nextToken());
				// -1 로 초기화 , 방문할시 0처리 
				dp[i][j] = -1;
			}
		}
		
		System.out.println(searchDown(0,0));
	}
	private static int searchDown(int x, int y) {
		if(x == N-1 && y == M-1) {
			return 1;
		}
		// dfs 방식이므로 dp가 -1 아니라면 이미 탐색한 경로이므로 return dp;
		if(dp[x][y] != -1) {
			return dp[x][y];
		}
		
		dp[x][y] = 0;
		for(int i = 0 ; i < 4 ; i++) {
			int nx = x + dx[i];
			int ny = y + dy[i];
			if(0 > nx || nx >= N || 0>ny || ny>= M || map[x][y] <= map[nx][ny]) continue;
			// 가능한 경로를 dp += 1
			dp[x][y] += searchDown(nx, ny);
		}
		return dp[x][y];
	}
}