[BOJ] 1520 : 내리막길

Question

---

Solution

• dfs만을 가지고 풀면 최악의 경우 4^(500 * 500)을 탐색하게 된다. 따라서 dfs + dp를 활용한다.
• dp 배열의 값을 ‘-1’로 초기화한다. ‘0’일 경우는 이미 탐색하고 경로가 없을 경우, ‘1 ~’ 이상은 경로의 수가 되겠다.

---

Cord

#include <iostream>

#define MAX 501

using namespace std;

int m, n;
int cnt;

int map[MAX][MAX];
int dp[MAX][MAX];

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

int dfs(int _x, int _y)
{	
	if (_x == n - 1 && _y == m - 1) { return 1; }
	if (dp[_y][_x] != -1) { return dp[_y][_x]; }

	dp[_y][_x] = 0;

	for (int i = 0; i < 4; i++)
	{
		int nextX = _x + dx[i];
		int nextY = _y + dy[i];

		if (0 <= nextX && nextX < n && 0 <= nextY && nextY < m)
		{
			if (map[_y][_x] > map[nextY][nextX])
			{
				dp[_y][_x] = dp[_y][_x] + dfs(nextX, nextY);
			}
		}
	}
	return dp[_y][_x];
}

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

	// 지도의 세로 x 가로 : m x n
	cin >> m >> n;

	// 맵 입력
	for (int i = 0; i < m; i++)
	{
		for (int j = 0; j < n; j++)
		{
			cin >> map[i][j];
			dp[i][j] = -1;
		}
	}

	// dfs 실행
	cnt = dfs(0, 0);

	// 출력
	cout << cnt;

	return 0;
}

---

Result