[백준] 1520. 내리막 길 (Java)

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

1520번: 내리막 길

 

 

💡 DFS + DP

 

✔️ 문제 리뷰

처음에는 DFS를 사용해서 visited 2차원 배열로 방문 체크를 하여 풀었다. 하지만 이 문제는 visited 대신 dp 2차원 배열을 사용해 기존에 방문하지 않았던 칸만 탐색해야 하는 문제였다. 단순 DFS로만 풀면 시간초과가 발생한다.

 

 

✔️ 문제 풀이

1. 초기 dp 2차원 배열을 모두 -1로 초기화한다.
2. (0,0)부터 DFS를 시작하여 dp[x][y] 값이 -1인 경우(방문하지 않은 경우)에 사방탐색을 한다.
3. 현재 값보다 작으면 dp[x][y]값에 DFS 결과를 넣는다.
4. 탐색을 모두 마쳤다면, return dp[x][y]한다.

 

✅ 정답 코드

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

public class Main {

	static int M,N;
	static int[][] board, dp;
	static int[] dx = {-1,1,0,0};
	static int[] dy = {0,0,-1,1};
	
	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st;
		
		st = new StringTokenizer(br.readLine());
		
		M = Integer.parseInt(st.nextToken()); // row
		N = Integer.parseInt(st.nextToken()); // col

		board = 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++) {
				board[i][j] = Integer.parseInt(st.nextToken());
				dp[i][j] = -1;
			}
		} // input end
		
		System.out.println(solve(0, 0));
	}
	
	private static int solve(int x, int y) {
		
		if(x == M-1 && y == N-1) return 1;
		
		if(dp[x][y] == -1) {
			dp[x][y] = 0;
			
			for(int d=0;d<4;d++) {
				int nx = x + dx[d];
				int ny = y + dy[d];
				
				if(!is_valid(nx, ny)) continue;
				
				if(board[nx][ny] < board[x][y]) {
					dp[x][y] += solve(nx, ny);
				}
				
			}
		}
		
		return dp[x][y];
	}

	private static boolean is_valid(int r, int c) {
		if(r<0 || c<0 || r>=M || c>=N) return false;
		return true;
	}

}