[백준-그래프탐색-dfs] 1520 - 내리막길

코드

package dfs;

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

public class Pr1520내리막길_복습2 {
	static int[] dx = {-1, 0, 1, 0};
	static int[] dy = {0, 1, 0, -1};
	static int M;
	static int N;
	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());	//열
		
		int[][] board = new int[M+1][N+1];
		DP = new int[M+1][N+1];
		for (int i=1; i<M+1; i++) {
			st = new StringTokenizer(br.readLine());
			for (int j=1; j<N+1; j++) {
				board[i][j] = Integer.parseInt(st.nextToken());
				DP[i][j] = -1;
			}
		}
		System.out.println(dfs(1,1, board));
	}
	static int dfs(int x, int y, int[][] board) {
		
		//base case
		if (x==M && y==N) {
			return 1;
		}
		
		//recursive case
		if(DP[x][y] == -1) {
			DP[x][y] = 0; //x,y 방문
			
			for (int i=0; i<4; i++) {
				//탐색할 다음 x,y좌표
				int nx = x + dx[i];
				int ny = y + dy[i];
				
				//탐색가능한지 검출
				if (nx>=1 && nx<=M && ny>=1 && ny<=N) {
					if (board[nx][ny] < board[x][y]) {
						//다음 노드 탐색
						DP[x][y] += dfs(nx, ny, board);
						
						//그림을 그려보면 호출된놈의 리턴값은 호출한놈에 저장되는 것이 맞다.
					}
				}
			}
			
		}
		return DP[x][y];
	}
}