백준 1520 내리막길 c++ // top-down dp, dfsDp, 상하좌우탐색 문제점

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

1520번: 내리막 길

1. top-down dp

위에서부터구하는 dp를말한다.

재귀로 구현한다.

fibo(15)=fibo(14)+fibo(13) ...

 

2. bottom-up dp

위에서부터구하는 dp를말한다.

반복문으로 구현한다.

fibo(3)=fibo(1)+fibo(2) / fibo(4)= ... / fibo(15)= ...

 

3. 상하좌우탐색 문제점

-> or 아래 or 5시대각선 탐색은 배열을 i,j 한칸씩 탐색하면서 dp만으로 충분하다.

but, 위, 좌측으로 이동하는경우 배열을 한칸씩 탐색하는것으로 부족하다. dfs를 사용해야한다.

 

4. dfs문제점

1. 완탐의 경우 상하좌우(4)^500(가로)*500(세로)의 경우의 수가 든다.

해결 : dp?

 

5. dp로 풀수있는가?

1. 작은문제로 쪼개도 동일한 풀이법인가? O

(0,0)50에서 10가는것과 , (1,1)50에서 10가는것이 동일한 풀이법이다.

 

2. 이미 구해놓은 값을 재사용가능한가? ㅇ

20에서 10에가는 경우의 수를 재사용 가능하다!

즉, dp[20]이 존재하는경우 그냥 그 값을 사용하면된다. 20에서 10가는방법을 다시 계산할 필요가 없다.

 

3. 탑다운? 바텀업?

길이 상하좌우인경우, 예측이 힘든경우는 탑다운을 사용한다.

 

6.의사코드

0. dp 테이블정의 : dp[i][j] : (i,j)~(n-1,m-1)로 가는 경로의 수

1. dp를 -1로 초기화 => 최초방문 즉 탐색해야함표시

문제 : 0으로 초기화하는경우 -> 최초방문인지 경로가0개인지 구분이안됨.

 

*dfs

2. 메모가있는경우, memo 리턴

3. 최초방문인경우, 경로0개로 초기화후 진행

해당(y,x)에서 정답으로 가는 경우의수 == 나를 둘러싼 상하좌우의 자식들 경로의수의 합임

4. 그렇게 구한 경로의수를 리턴

 

6.1. 참고자료(리턴되면서 dp 테이블에 누적합이 된다)

위의 코드에서 재귀 호출에 따라 dp 테이블의 값이 어떻게 달라지는지 분석해보았다. (비어있는 칸은 -1로 초기화 되어 있다고 가정하자.)

dp[0][0]은 -1로 초기화 된 상태이므로 (b)에서 리턴되지 않고 다음 줄로 넘어간다.

dp[0][0] = 0로 다시 초기화 되고, 상하좌우에 자신보다 작은 값이 존재하는지 탐색한다.

자신보다 작은 값을 발견하면 그 위치에 대해 dfs 함수를 재귀 호출한다. 이런 식으로 depth가 깊어지면서 재귀 호출을 반복하다가 (3, 4)에 도달하면 1을 리턴한다. --- (a)

이 리턴값은 해당 함수를 재귀 호출했던 그때 당시의 dp[x][y]에 더해진다. 즉, 해당 함수를 재귀 호출하기 바로 이전 스택 프레임에 반영된다.

위의 그림에서는 함수가 리턴을 하면, 안쪽 프레임이 하나씩 삭제된다고 보면 된다. 그러면서 리턴값은 바로 바깥쪽 프레임에 반영된다.

계속 리턴하다가 다시 (0, 0)으로 돌아오면 50보다 작은 값이 35 말고 45도 있기 때문에 이번에는 그쪽 방향으로 이동한다. 아까처럼 자신보다 작은 값을 발견할 때마다 재귀 호출을 반복하면서 dp 테이블을 채워나간다. 그러다가 (3, 3)에 도달하면 현재 dp 테이블에 채워진 값이 -1이 아니기 때문에 (b)에서 dp[x][y] 자체를 리턴한다. 그 리턴값은 바로 이전 스택 프레임에 반영된다.

그리고 (0, 3)에 도달하면, 32보다 작은 값이 20 말고 30도 있기 때문에, 그쪽 방향으로 이동한다. 이번에도 자신보다 작은 값을 발견할 때마다 재귀 호출하다가 (1, 3)에 도달하면 dp 테이블에 이미 저장된 값이 있기 때문에 더 이상 탐색을 진행하지 않고 dp[1][3]을 그대로 반환한다.

재귀 호출을 했던 순서의 역방향으로 dp 테이블에 리턴값이 더해지게 되고, 결과적으로 (0, 0)으로 돌아와서 dp[0][0]에 저장된 3이 리턴되어 결과가 출력된다. --- (c)

이런 식으로 큰 문제를 작은 문제로 나눠서 작은 문제들의 해를 재귀적으로 구하고, 이를 취합하여 큰 문제의 해를 구하는 게 dp의 하향식 접근법이다. 그리고 한 번 계산된 결과를 기억하기 위해서 메모이제이션 기법을 이용한다. (이 문제에서는 현재 칸에서 목적지까지 도달하는 경로의 개수가 dp 테이블에 저장된다.)

출처 : https://velog.io/@jxlhe46/%EB%B0%B1%EC%A4%80-1520%EB%B2%88.-%EB%82%B4%EB%A6%AC%EB%A7%89%EA%B8%B8

 

7. 전체코드

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
int dp[504][504],a[504][504]; //dp[i][j] : (i,j)~(n,m)까지 경로의 수
int n,m;
int dy[] = { 1,0,-1,0 };
int dx[] = { 0,1,0,-1 };

int dfs(int y, int x) {
	//1. 메모가 있으면 메모활용
	if (dp[y][x] != -1) {
		return dp[y][x];
	}
	//2. 최초방문인경우 초기화(경로가 0개로)후 자식탐색
	dp[y][x] = 0;
	for (int k = 0; k < 4; ++k) {
		int ny = y + dy[k];
		int nx = x + dx[k];
		if (ny < 0 || ny >= n || nx < 0 || nx >= m) continue;
		if (a[y][x] <= a[ny][nx]) continue;
		dp[y][x] += dfs(ny, nx);
		//(y,x)~(n,m)까지의 경로의 수 == '시그마' 내 상하좌우 자식~(n,m)까지의 경로의수
	}
	return dp[y][x]; //그렇게 만들어진 결과 결과 리턴
}
int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cin >> n>>m;
	
	for (int i = 0; i < n; ++i) {
		for (int j = 0; j < m; ++j) {
			cin >> a[i][j];
		}
	}
	fill(&dp[0][0], &dp[0][0] + 504 * 504, -1);
	dp[n-1][m-1] = 1;
	
	dfs(0, 0);
	cout << dp[0][0];

	/*for (int i = 0; i < n; ++i) {
		for (int j = 0; j < m; ++j) {
			cout << dp[i][j] << " ";
		}
		cout << "\n";
	}*/

	return 0;
}