<Baekjoon> #1520 Dyamic Programming, DFS_내리막 길 c++

#1520 내리막길

💡Summary & Idea

• 처음 칸에서 상하좌우 이웃한 곳을 탐색해서 제일 아래 칸으로 내려간다는 점에서 dfs를 이용해 풀어야 한다는 것을 알 수 있다
• 처음에 dfs만을 이용해 풀었다가 시간 초과가 났다. map의 크기가 최대 500*500이므로 완전탐색 dfs 방법으로 풀면 최악의 경우 4^(500*500)의 탐색을 해야한다
  => DFS + DP 방법으로 해결한다

✏️1. Initialize dp

• 동적 계획법 알고리즘을 만드는 첫 단계는 해당 문제를 재귀적으로 해결하는 완전 탐색 알고리즘을 만드는 것이다.
• 참조적 투명 함수인 경우 메모이제이션을 적요해 중복된 연산을 없댄다

• dp[a][b]=c 라고 두고, (a,b)에서 (M-1, N-1)까지 갈 수 있는 경우는 c가지라 한다
• 먼저 dp[]는 -1로 초기화하고 한 번도 방문하지 않았다는 표시를 한다
• dp[y][x]==-1이어서 (y,x)지점에서 탐색을 시작해야할 때 dp[y][x]=0 으로 두고 탐색을 시작한다. 현재 탐색을 시작했지만 (y,x)지점에서 (M-1, N-1)까지 갈 수 있는 경우는 없다는 뜻이다

✏️2. DFS

• 먼저 dp를 사용하지 않은 완전 탐색 알고리즘을 살펴보자

int cnt = 0;
void dfs1(int y, int x) {
	if (y == M - 1 && x == N - 1) cnt++;
	for (int dir = 0; dir < 4; dir++) {
		int ny = y + dy[dir];
		int nx = x + dx[dir];

		if (ny < 0 || nx < 0 || ny >= M || nx >= N) continue;
		if (map[y][x] > map[ny][nx])
			dfs1(ny, nx);
	}
}

1. (y,x)가 (M-1, N-1)에 도달했을 경우 카운트 해준다
2. 현재 위치 (y,x)를 기준으로 네 방향으로 탐색해서 다음 방향이 현재 자신의 크기보다 작다면 (내리막길이라면) 다시 그 다음지점에서 dfs 탐색을 반복한다
3. 이미 탐색했던 곳을 중복해서 탐색하게 된다

• dfs + dp 탐색을 살펴보자

int dfs2(int y, int x) {
	if (y == M - 1 && x == N - 1) return 1;
	if (dp[y][x] != -1) return dp[y][x];

	dp[y][x] = 0;
	for (int dir = 0; dir < 4; dir++) {
		int ny = y + dy[dir];
		int nx = x + dx[dir];

		if (ny < 0 || nx < 0 || ny >= M || nx >= N) continue;
		if (map[y][x] > map[ny][nx])
			dp[y][x] += dfs2(ny, nx);
	}
	return dp[y][x];
}

1. (y,x)가 (M-1, N-1)에 도달했을 경우 1가지 경우를 더해준다
2. dp[y][x]!=-1 이라는 뜻은 이미 (y,x)지점에서 (M-1, N-1)까지 가는 탐색을 했다는 뜻이고 그 경우는 총 dp[y][x]가지라는 뜻이다
3. 탐색을 시작한다는 의미로 dp[y][x]=0로 만들어준다
4. dp[y][x]+=dfs2(ny,nx) : bottom-up 방식으로 (M-1, N-1)에서 가장 가까운 위치부터 탐색한다

🔖Source Code

#include <iostream>
#include <vector>
#include <string.h>

using namespace std;

const int MAX = 501;

int M, N;
vector<vector<int>>map;
int dp[MAX][MAX];

int dy[] = { 0,0,1,-1 };
int dx[] = { 1,-1,0,0 };

int dfs2(int y, int x) {
	if (y == M - 1 && x == N - 1) return 1;
	if (dp[y][x] != -1) return dp[y][x];

	dp[y][x] = 0;
	for (int dir = 0; dir < 4; dir++) {
		int ny = y + dy[dir];
		int nx = x + dx[dir];

		if (ny < 0 || nx < 0 || ny >= M || nx >= N) continue;
		if (map[y][x] > map[ny][nx])
			dp[y][x] += dfs2(ny, nx);
	}
	return dp[y][x];
}

int cnt = 0;
void dfs1(int y, int x) {
	if (y == M - 1 && x == N - 1) cnt++;
	for (int dir = 0; dir < 4; dir++) {
		int ny = y + dy[dir];
		int nx = x + dx[dir];

		if (ny < 0 || nx < 0 || ny >= M || nx >= N) continue;
		if (map[y][x] > map[ny][nx])
			dfs1(ny, nx);
	}
}

void input() {
	memset(dp, -1, sizeof(dp));
	cin >> M >> N;
	map = vector<vector<int>>(M, vector<int>(N));
	for (int i = 0; i < M; i++)
		for (int j = 0; j < N; j++)
			cin >> map[i][j];
}
int main() {
	input();
	//dfs1(0, 0);
	//cout << cnt << endl;
	cout<<dfs2(0, 0)<<endl;
	return 0;
}