[백준 1520번] 내리막 길 (java)

사용한 방법 : DFS, DP

 

문제 1.

처음에는 DFS만으로 문제를 풀었는데 메모리 초과가 나왔다. 생각을 해보니 DFS만으로 문제를 풀면 이미 지나갔던 경로를 다시 지나가야 한다는 문제점이 생기게 된다.

예를 들어 32 -> 30 -> 25 -> 20 -> 17 -> 15 -> 10 경로를 먼저 거친 후 재귀를 끝내고 다시 32로 돌아와서 32 -> 20 -> 17 -> 15 -> 10 경로를 구해야 할 때, 그 이전에 20 -> 17 -> 15 -> 10 으로 향하는 경로의 수를 구한 상태임에도 불구하고 갔던 경로를 또 탐색하게 된다.

public static int dfs(int sm,int sn) {

	int count=0;

	for (int i = 0; i < 4; i++) {
		int m = sm + y[i];
		int n = sn + x[i];

		if ((1 <= m && m <= M) && (1 <= n && n <= N)) {

			if (graph[m][n] < graph[sm][sn]) {
				if (m == M && n == N) 
				   count += 1;				
				else
				   count += dfs(m, n);
			}
		}
	}

	return count;
}

그래서 중복되는 부분을 없애기 위해서 DP를 사용하기로 한다.

처음에는 DFS와 DP를 동시에 사용한다는 점이 어렵게 느껴졌다.

DFS만으로도 복잡한데 DP를 어떻게 사용하지?

 

일단 중복되는 부분을 없애기 위해서는 위의 예에서 20 -> ~ -> 10으로 가는 경로의 수를 이미 구하였다면,

dp[1][3](20의 위치 (1,3)) 에 20 -> ~ -> 10으로 가는 경로의 수를 저장해두는 방식으로 시도하였다.

그러면 다음번에는 count+=dfs(m,n)이 아니라 dp[sm][sn]+=dp[m][n]을 해주면 되는 것이다.

 

 

문제 2.

그런데 또 메모리 초과가 나왔다. DFS와 DP 모두 사용하였는데도 메모리 초과가 나왔다..

이 문제는 검색을 통해서 힌트를 얻을 수 있었다. 처음에 dp 2차원 배열을 초기화할 때 0으로 초기화가 된다.

public static int dfs(int sm,int sn) {

	for (int i = 0; i < 4; i++) {
		int m = sm + y[i];
		int n = sn + x[i];

		if ((1 <= m && m <= M) && (1 <= n && n <= N)) {

			if (graph[m][n] < graph[sm][sn]) {
				if (m == M && n == N) {
					dp[sm][sn] += 1;
				}
				if (dp[m][n] > 0)
					dp[sm][sn] += dp[m][n];
				else
					dp[sm][sn] += dfs(m,n);
			}
		}
	}

	return dp[sm][sn];
}

그런데 0으로 초기화를 하게 되면 dp[m][n]=0일 때, 이미 탐색을 했는데 경로의 수가 0인 것인지 아니면 아직 탐색을 하지 않아서 0인 것인지 구분을 할 수 없게 된다. 여기서 문제는 이미 탐색을 했는데 경로의 수가 0인 경우, 또 다시 탐색을 한다는 점이다. 중복을 없애기 위해 DP를 사용했는데 여전히 중복되어 경로를 탐색하는 문제점이 남아 있는 것이다.

 

그렇다면 해결책은?

처음에 dp를 -1로 초기화를 해주면, 이미 탐색을 했는데 경로의 수가 0인 경우와 아직 경로 탐색을 하지 않은 경우가 구별이 되며 재귀로 넘어가지 않고 dp값을 더해주는 조건을 dp[m][n]>0 에서 dp[m][n]>=0으로 변경해주면 된다.

그러면 dp[m][n]=0이면 이미 탐색했는데 경로의 수가 0인 것으로 간주하여 또 중복해서 탐색하지 않고 넘어간다.

 

 

전체코드 : 

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.Stack;

public class Main {

	static int[][] graph;
	static int[][] dp;
	static int M, N;
	static int[] x = { 0, 1, 0, -1 };
	static int[] y = { 1, 0, -1, 0 };

	public static void main(String[] args) throws Exception {

		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

		String[] s = br.readLine().split(" ");
		M = Integer.parseInt(s[0]);
		N = Integer.parseInt(s[1]);
		graph = new int[M + 1][N + 1];
		dp = new int[M + 1][N + 1];

		for (int i = 1; i <= M; i++) {
			s = br.readLine().split(" ");
			for (int j = 1; j <= N; j++) {
				graph[i][j] = Integer.parseInt(s[j - 1]);
				dp[i][j] = -1;
			}
		}
		int res = dfs(1,1);
		bw.write(res + "\n");
		bw.flush();

	}

	public static int dfs(int sm,int sn) {

		dp[sm][sn] = 0;

		for (int i = 0; i < 4; i++) {
			int m = sm + y[i];
			int n = sn + x[i];

			if ((1 <= m && m <= M) && (1 <= n && n <= N)) {

				if (graph[m][n] < graph[sm][sn]) {
					if (m == M && n == N) {
						dp[sm][sn] += 1;
					}
					if (dp[m][n] >= 0) // >에서 >=로 바꿈
						dp[sm][sn] += dp[m][n];
					else
						dp[sm][sn] += dfs(m, n);
				}
			}
		}

		return dp[sm][sn];
	}
}