백준 1520번: 내리막 길

문제 설명

• https://www.acmicpc.net/problem/1520
• (1,1)에서 (N,M)까지 조건을 만족하면서 이동할 수 있는 경로가 몇 개인지 구하는 문제입니다.
  • 현재 위치보다 더 적은 숫자로만 이동할수 있다가 조건입니다.

접근법

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

기본 형태

public static int DFS(int x, int y){
	// 탈출
	if(목적지 도착){
	    return ?;
    }
    // dp에 값이 존재하면 그대로 사용
    if(dp에 값이 존재하면){
    	return dp[x][y]
    }
    // 값 초기화
    dp[x][y] = ?; 
    // 4방탐색
    for(int d = 0; d < 4; d++) {
    	int nx = x + dx[d];
        int ny = y + dy[d];
        if(조건을 만족하면){
        	dp[x][y] = Math.max(dp[x][y],DFS(nx,ny)로 계산한 다음값);
        }
    }
    return dp[x][y];
}

정답

import java.util.*;
import java.io.*;

public class Main {
	static int[] dx = { 0, 1, 0, -1 };
	static int[] dy = { 1, 0, -1, 0 };
	static int N, M;

	public static void main(String[] args) throws IOException {
		Scanner sc = new Scanner(System.in);
		N = sc.nextInt();
		M = sc.nextInt();
		int[][] board = new int[N][M];
		int[][] dp = new int[N][M];

		for (int i = 0; i < N; i++) {
			Arrays.fill(dp[i], -1); // dp배열 초기화
			for (int j = 0; j < M; j++) {
				board[i][j] = sc.nextInt();
			}
		}
		DFS(0, 0, board, dp);
		System.out.println(dp[0][0]);
//		for (int i = 0; i < N; i++) {
//			System.out.println(Arrays.toString(dp[i]));
//		}
	}

	public static int DFS(int x, int y, int[][] board, int[][] dp) {
		// 마지막 위치에 도달했으면 1 반환
		if (x == N - 1 && y == M - 1) {
			return 1;
		}

		// 이미 저장된 값이 있다면 그대로 사용
		if (dp[x][y] != -1) {
			return dp[x][y];
		}

		// 최초 0에서 시작
		dp[x][y] = 0;

		for (int d = 0; d < 4; d++) {
			int nx = x + dx[d];
			int ny = y + dy[d];
			if (0 <= nx && nx < N && 0 <= ny && ny < M && board[x][y] > board[nx][ny]) {
				dp[x][y] = Math.max(dp[x][y], dp[x][y] + DFS(nx, ny, board, dp));
			}
		}

		return dp[x][y];
	}

}

비슷한 문제

욕심쟁이 판다 | 풀이