[백준] 1520 내리막 길 - 재귀(DFS) + DP JAVA

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

1520번: 내리막 길

코드설명

DFS와 DP를 활용하는 문제입니다.

 

처음에 문제를 보고 BFS로 Visited[][][4] 로 처리하였지만, 이렇게 할경우 같은방향으로 들어오는경우도 처리가 올바르게 되지 않아 작동하지 않습니다.

그렇기에, 위와 같은 BFS와 중복처리로도 해결되지 않습니다.

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

public class Main {
	public static int N, M;
	public static int answer = 0;
	public static int[][] arr;
	public static int[] dx = { -1, 1, 0, 0}; //상하좌우
	public static int[] dy = { 0, 0, -1, 1};
	public 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());
    	
    	N = Integer.parseInt(st.nextToken());
    	M = Integer.parseInt(st.nextToken());
    	
    	arr = 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++) {
    			arr[i][j] = Integer.parseInt(st.nextToken());
    			dp[i][j] = -1;
    		}
    	}
    	
    	answer = DFSWithDp(0, 0);
    	System.out.println(answer);
	}
	
	public static int DFSWithDp(int startX, int startY) {
		if( startX == N -1 && startY == M - 1) {
			return 1;
		}
		if(dp[startX][startY] != -1) { //이미 계산된 구간이라면 해당 구간에서 (N, M)까지의 경로의 개수를 바로 가져올 수 있습니다.
			return dp[startX][startY];
		}
		dp[startX][startY] = 0;  //해당 점에서 (N,M)까지 0 이라고 초기화시키며 방문처리를 합니다.
		
		for(int dir= 0; dir<4;dir++) {
			int nx = startX + dx[dir];
			int ny = startY + dy[dir];
			
			if(nx < 0 || nx >= N || ny < 0 || ny >= M) continue; //범위체크
			if(arr[startX][startY] <= arr[nx][ny] ) continue; //만약 내리막길이 아니라면 중단
			dp[startX][startY] += DFSWithDp(nx, ny ); //내리막길일경우 실행. 다음 위치가 이미 계산된 경우라면 DP배열을 통해 값을 바로 가져옵니다.
		}
		
		return dp[startX][startY]; //만약 해당 지점에서 더이상 이동할 수 없다면 본인의 DP값을 반환하여 종료시킵니다.
		
	}
	
}