188. 1520(내리막 길) - 자바

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

class Main {
	static int M;
	static int N;
	static int[][] dxdy = { { 1, 0 }, { -1, 0 }, { 0, -1 }, { 0, 1 } };
	static int[][] dp;
	static int[][] travelMap;

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		String[] tmp = br.readLine().split(" ");
		M = Integer.parseInt(tmp[0]);
		N = Integer.parseInt(tmp[1]);

		travelMap = new int[M][N];
		dp = new int[M][N];

		for (int i = 0; i < M; i++) {
			tmp = br.readLine().split(" ");
			for (int j = 0; j < N; j++) {
				travelMap[i][j] = Integer.parseInt(tmp[j]);
				dp[i][j] = -1;
			}
		}

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

	}

	private static int dfs(int x, int y) {

		// 도착지점
		if (x == M - 1 && y == N - 1)
			return 1;

		// 만약 방문하지 않았다면
		if (dp[x][y] == -1) {
			dp[x][y] = 0;

			// 0 => x , 1 => y
			for (int[] xy : dxdy) {
				if ((0 <= x + xy[0] && x + xy[0] < M) && (0 <= y + xy[1] && y + xy[1] < N)) {
					if (travelMap[x + xy[0]][y + xy[1]] < travelMap[x][y]) {
						dp[x][y] += dfs(x + xy[0], y + xy[1]);
					}
				}
			}
		}
		return dp[x][y];

	}
}

문제요약

(0,0)에서 마지막 지점까지 가는데 상하좌우로 값이 더 작은 쪽으로 이동하라.

설명

이 문제는 깊이우선 탐색(DFS)과 동적계획법(DP) 개념을 사용해야 풀 수 있다.

깊이우선 탐색으로는 해당 분기에서 모든 노드를 비교하여 완벽하게 탐색후 다음으로 넘어 갈 것이다.

그러면 모든 노트 탐색으로 인해 시간초과가 발생할 것이다.

 

따라서 하나의 큰 문제를 작은 단위로 만들어 풀어줌(dp)과 동시에 방문을 계산을 했음을 알려주면서 연산 횟수를 줄여준다.

먼저 빨간색 부분은 출발부분, 초록색 부분은 도착부분이다.

 

도착지점(초록색)은 x와 y좌표가 M-1, N-1일 것이다.

따라서 도착지점은

		// 도착지점
		if (x == M - 1 && y == N - 1)
			return 1;

로 알려준다.

 

그리고 우리는 위에서 말한것처럼 dp를 통해서 방문여부도 확인할 것이다.

따라서 -1로 방문하지 않은 경로임을 알려주자.

		for (int i = 0; i < M; i++) {
			tmp = br.readLine().split(" ");
			for (int j = 0; j < N; j++) {
				travelMap[i][j] = Integer.parseInt(tmp[j]);
				dp[i][j] = -1;
			}
		}

 

dp가 -1이라는 것은 방문하지 않았다는 뜻이다.

연산이 정상적으로 실행된다.

일단 해당 경로가 목적지까지 갈 수 없는 경로일 수 있다. (상하좌우에 자신보다 낮은 값이 없을경우)

그 경우를 위해 처음에 0을 선언하고 실제로 목적지까지 도달이 불가능하면 0을 반환할 것이다. 

		// 만약 방문하지 않았다면
		if (dp[x][y] == -1) {
        	// 목적지까지 갈 수 없는 경우는 0으로 반환
			dp[x][y] = 0;

 

그럼 이제 초기 셋팅은 끝났고 상하좌우를 실제롤 비교해야한다.

자신 기준 +(1,0)은 상  +(-1,0)은 하  +(0,-1)은 좌  +(0,1)은 우 이다.

상하좌우 값이 M,N의 범위를 벗어나지 않는다면 첫번째 조건에 만족한다.

두번째로는 상하좌우(x+dx,y+dy)가 자신(x,y)보다 작으면  앞으로 나아간다.

			// 0 => x , 1 => y
			for (int[] xy : dxdy) {
				if ((0 <= x + xy[0] && x + xy[0] < M) && (0 <= y + xy[1] && y + xy[1] < N)) {
					if (travelMap[x + xy[0]][y + xy[1]] < travelMap[x][y]) {
						dp[x][y] += dfs(x + xy[0], y + xy[1]);
					}
				}
			}

 

이런식으로 목적지(도착지점)에 도달한 경우에는 계속 +1이 되어 우리가 구하고자 하는 최종 결과를 도출해 낼 수 있다.