[DP, DFS] 백준 1520 내리막길 C++

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

1520번: 내리막 길

---

---

풀이 : 

일반적인 DFS로 풀었다가 시간초과나서 한참을 고민한 문제.. 결국 인터넷에서 풀이를 찾아봤는데 핵심은 DP를 쓰는 것이다 백트래킹인가 해서 삽질을 몇시간 했는데 결국 풀지 못함.. 

결국 DP배열로 경로를 저장해두면 쉽게 풀린다. 경로를 저장한다는 개념이 좀 추상적인데 

결국 map[0][0] 에서 map[m-1][n-1] 까지 가는 경로의 수를 구하는 문제 이므로

dp[i][j] 란 (i, j)에서 도착지점 (map[m-1][n-1]) 까지 갈수있는 경로의 수 라고 생각하면 된다.

결국 구해야 되는 값은 dp[0][0]일 것이다. dfs탐색을 통해 값을 구할 수 있는데 이때 주의해야 할 점은 방문시 경로가 없는경우 dp[i][j] = 0 이렇게 저장될 텐데 global로 선언한 dp배열의 초기값열이 0으로 채워져 있다. 이를 구분해줘야 한다. 정리하자면

일반적인 dfs탐색 = > 중복탐색으로 인한 시간초과 = > dp사용으로 방문한 노드의 값을 저장해둠(메모리제이션) = > 방문한 노드는 dp에 값을 저장해 뒀으므로 그대로 리턴하면 된다. => 이때 방문하지 않은 dp배열의 초기값 0 경로가 0인 배열의 값도 0이므로 구분 = > 구분을 위해 vis배열을 둬서 방문처리를 해준다!

 

code :

#include <iostream>

using namespace std;

int m, n;
int map[502][502];
int dp[502][502];
int vis[502][502];
int dx[4] = { 1,0,-1,0 };
int dy[4] = { 0,1,0,-1 };


int dfs(int i, int j) {
	if (i == m - 1 && j == n - 1) return 1;
	if (vis[i][j]) return dp[i][j];

	vis[i][j] = 1;
	for (int k = 0; k < 4; k++) {
		int nx = i + dx[k];
		int ny = j + dy[k];
		if (nx >= 0 && nx < m && ny >= 0 && ny < n) {
			if (map[nx][ny] < map[i][j]) {
				dp[i][j] += dfs(nx, ny);
			}
		}
	}

	return dp[i][j];

}
int main() {
	
	cin >> m >> n;
	for (int i = 0; i < m; i++) {
		for (int j = 0; j < n; j++) {
			cin >> map[i][j];
		}
	}
	
	cout << dfs(0, 0) << endl;
	
}