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

- 문제 설명

 

 

- 문제 풀이

DFS를 사용해야 하는 문제이다. 그러나 단순히 DFS만 사용해서 풀면 탐색의 양이 무수히 많아지기 때문에 시간초과가 발생한다. 때문에 DFS + DP 메모제이션을 추가로 활용해줘야 하는 문제이다.

 

우선 상하좌우를 검색할때 현재 노드보다 값이 작은 곳만 향할 수 있어야 하기 때문에

배열의 크기를 arr[502][502]로 해주고, 최대값이 10000이므로 10001로 초기화 해주었다.

 

예제로 예시를 든다면 아래 표와 같이 나타낼 수 있다.

10001	10001	10001	10001	10001	10001	10001
10001	50	45	37	32	30	10001
10001	35	50	40	20	25	10001
10001	30	30	25	17	28	10001
10001	27	24	22	15	10	10001
10001	10001	10001	10001	10001	10001	10001

 

dp배열 또한 지도값을 저장한 arr배열과 비교할 때 탐색하는 값이 같도록 dp[502][502]로 초기화 해주었다.

여기서 dp의 값은 dp[x][y] = z 라고 했을 때 z는 좌표 x, y에서 도착지인 M, N까지 갈 수 있는 경우의 수 이다.

그러면 결론적으로 dp[1][1]이 답이라 할 수 있다.

 

3	2	2	2	1
1	-1	-1	1	1
1	-1	-1	1	-1
1	1	1	1	-1

 

또한 dp의 초기값을 -1로 초기화 해준다. 탐색 도중 -1은 아직 탐색해보지 않았다는 것을 의미하고, 최종적으로 남아있는 -1 좌표들은 탐색할 수 없는 곳을 의미한다. 또한 dp[M][N] = -1 인 이유는 DFS를 할 때 x == M && y == N인 구간에서 먼저 return을 해버리기 때문에 dp[x][y] = 0으로 초기화 되지 않기 때문이다.

 

 

- 코드

#include <iostream>
#include <algorithm>
using namespace std;

int M, N, H = 0;
int arr[502][502];
int dp[502][502]; // dp[x][y] = z에서 z는 x, y에서 M, N까지 갈 수 있는 경우의 수

int depth(int x, int y)
{
	if (x == M && y == N)
	{
		return 1;
	}

	if (dp[x][y] != -1)
		return dp[x][y];

	dp[x][y] = 0;

	// 상하좌우에서 갈 수 있는 방향으로 깊이 우선 탐색(DFS)를 한다.
	if (arr[x + 1][y] < arr[x][y])
	{
		dp[x][y] = dp[x][y] + depth(x + 1, y);
	}
	if (arr[x - 1][y] < arr[x][y])
	{
		dp[x][y] = dp[x][y] + depth(x - 1, y);
	}
	if (arr[x][y + 1] < arr[x][y])
	{
		dp[x][y] = dp[x][y] + depth(x, y + 1);
	}
	if (arr[x][y - 1] < arr[x][y])
	{
		dp[x][y] = dp[x][y] + depth(x, y - 1);
	}
	return dp[x][y];
}

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);

	cin >> M >> N;
	fill(&arr[0][0], &arr[M+1][N+1]+1, 10001); // 여유공간을 실제 사용할 공간에서 향하지 않게 하기 위해
	for (int i = 1; i <= M; i++)
		for (int j = 1; j <= N; j++)
		{
			cin >> arr[i][j];
			dp[i][j] = -1; // -1은 아직 검사해보지 않은곳을 의미
		}

	H = depth(1, 1);

	cout << H;

	return 0;
}