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

문제

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

1520번: 내리막 길

 

해결방법

dfs와 dp를 사용해서 풀 수 있는 문제이다.

dp[x][y]에 저장되는 값은 (x, y)에서 (n-1, m-1)까지 가는 방법의 개수이다.

제일 왼쪽 위 (0,0)에서 현재 위치의 값보다 작은 방향으로 이동하면서 d[x][y] += dfs(nx,ny) 식을 통해 dfs를 돌려 다음 위치의 dp값을 받아오면 된다.

코드

#include <iostream>

using namespace std;

int n, m;
int map[501][501];
int dp[501][501];
bool visit[501][501];
int dx[4] = { 1,-1,0,0 }, dy[4] = {0,0,1,-1};

int dfs(int x, int y) {
	if (x == n - 1 && y == m - 1)
		return 1;
	if (visit[x][y]==true)
		return dp[x][y];

	visit[x][y] = true;
	for (int i = 0; i < 4; i++) {
		int nx = x + dx[i];
		int ny = y + dy[i];

		if (nx >= 0 && nx < n && ny >= 0 && ny < m) {
			if (map[nx][ny] < map[x][y])
				dp[x][y] += dfs(nx, ny);
		}
	}
	return dp[x][y];
}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(0), cout.tie(0);

	cin >> n >> m;

	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			cin >> map[i][j];
			dp[i][j] = 0;
		}
	}

	cout << dfs(0, 0);

	return 0;

}