[BOJ 1520] 내리막 길 (Java)

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

1520번: 내리막 길

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

public class Main_BOJ_1520 {
	static int[] dr= {-1,1,0,0};
	static int[] dc= {0,0,-1,1};
	static int M, N;
	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][N];
		dp=new int[M][N];
		for (int i = 0; i < M; i++) {
			st=new StringTokenizer(br.readLine());
			for (int j=0; j<N; j++) {
				map[i][j]=Integer.parseInt(st.nextToken());
				dp[i][j]=-1;
			}
		}
		System.out.println(dfs(0,0));

	}
	private static int dfs(int r, int c) {
		if (dp[r][c]!=-1) return dp[r][c];
		if (r==M-1 && c==N-1) return 1;
		dp[r][c]=0;
		for (int i=0; i<4; i++) {
			int nr=r+dr[i];
			int nc=c+dc[i];
			if (nr<0 || nc<0 || nr>=M || nc>=N) continue;
			if (map[r][c]>map[nr][nc]) dp[r][c]+=dfs(nr, nc);
		}
		return dp[r][c];
	}

}

DFS+메모이제이션 문제

 

dp[r][c]는 (r,c)에서 (M-1,N-1)까지 갈 수 있는 경우의 수를 나타낸다 

dp[r][c]가 -1이 아니면 이미 경우의 수가 나온 것이므로 바로 값을 리턴하고,

아닌 경우에는 주변 4방향에 대해 DFS 탐색을 해서 값을 누적시켜나간다.