1520: 내리막길 (DP)

풀이

dfs와 dp가 혼합된 문제이다.

visited배열을 boolean으로 생성하여 체크하지 않고 int로 생성하여 몇번 방문했는지 확인할 수 있게하였다.

0,0에서 시작해서 마지막 N-1, M-1에 도착하면 뒤로 돌아가면서 +하게 해주면 마지막에 도달할 수 있는 개수가 출력되게 된다.

 

코드

import java.util.Scanner;

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

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

		arr = new int[M][N];
		visited = new int[M][N];

		for (int i = 0; i < M; i++) {
			for (int j = 0; j < N; j++) {
				arr[i][j] = sc.nextInt();
				visited[i][j] = -1;
			}
		}

		System.out.println(dfs(0, 0));
	}

	public static int dfs(int i, int j) {
		if (i == M - 1 && j == N - 1)
			return 1;
		if (visited[i][j] == -1) {
			visited[i][j] = 0;
			for (int k = 0; k < 4; k++) {
				int nx = i + dx[k];
				int ny = j + dy[k];

				if (!(nx >= 0 && ny >= 00 && nx < M && ny < N))
					continue;

				if (arr[i][j] > arr[nx][ny])
					visited[i][j] += dfs(nx, ny);
			}
		}

		return visited[i][j];
	}
}