[백준][다이나믹] 1520 내리막길

내리막길은 DFS와 DP를 혼합하여 해결할 수 있는 문제이다. 

DFS를 이용하여 종점을 찾아서 

다시 돌아오면서 DP로 현재 경로에서 종점으로 갈 수 있는 경우를 메모한다. 

이미 메모한 곳을 찾으면 해당 값을 반환하면 된다. 

  * -1로 초기화 하여, 방문한 곳을 0으로 표시하면 다시 방문하지 않아도 된다. 

최종 위치에서 되돌아 가면서 경로를 표시하고, 

새로운 경로로 가면서 최종 위치로 도달할 수 있는 경로를 만나면 그값을 더하여 처리한다. 

<테스트 케이스>

10 10

20 19 18 17 16 15 14 13 12 11 

19 18 17 16 15 14 13 12 11 10 

18 17 16 15 14 13 12 11 10  9 

17 16 15 14 13 12 11 10  9  8 

16 15 14 13 12 11 10  9  8  7 

15 14 13 12 11 10  9  8  7  6 

14 13 12 11 10  9  8  7  6  5 

13 12 11 10  9  8  7  6  5  4 

12 11 10  9  8  7  6  5  4  3 

11 10  9  8  7  6  5  4  3  2 

	package sdk.backjun.dp;
	import java.util.Arrays;
	import java.util.Scanner;
	/**
	* 백준, 1520, 내리막길
	* https://www.acmicpc.net/problem/1520
	*
	* @author whitebeardk
	*
	*/
	public class Problem1520 {
	static int N;
	static int M;
	static int[][] moves = { { 0, 1 }, { 0, -1 }, { 1, 0 }, { -1, 0 } };
	public static void main(String[] args) {
	Scanner sc = new Scanner(System.in);
	M = sc.nextInt();
	N = sc.nextInt();
	int[][] maps = new int[M][N];
	for (int i = 0; i < M; i++) {
	for (int j = 0; j < N; j++) {
	maps[i][j] = sc.nextInt();
	}
	}
	sc.close();
	// 방문한곳 처리를 위해 -1로 초기화
	int[][] dp = new int[M][N];
	for (int[] arr : dp)
	Arrays.fill(arr, -1);
	// 종료지점 확인
	dp[M - 1][N - 1] = 1;
	findWay(maps, dp, 0, 0);
	System.out.println(dp[0][0]);
	// 경로 확인
	for (int i = 0; i < M; i++) {
	for (int j = 0; j < N; j++) {
	System.out.printf("%6d ", dp[i][j]);
	}
	System.out.println();
	}
	}
	public static int findWay(int[][] maps, int[][] dp, int x, int y) {
	// 종점 도달
	if (x == M - 1 && y == N - 1)
	return 1;
	// 이미 처리한 곳
	if (dp[x][y] >= 1 || dp[x][y] == 0)
	return dp[x][y];
	// 방문 처리
	if (dp[x][y] == -1) {
	dp[x][y] = 0;
	}
	for (int i = 0; i < moves.length; i++) {
	int nextX = x + moves[i][0];
	int nextY = y + moves[i][1];
	if (0 <= nextX && nextX < maps.length && 0 <= nextY && nextY < maps[0].length && maps[x][y] > maps[nextX][nextY]) {
	dp[x][y] += findWay(maps, dp, nextX, nextY);
	}
	}
	return dp[x][y];
	}
	}

view raw Problem1520.java hosted with ❤ by GitHub

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