백준 1520 / C++

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

이 문제는 처음에 dfs로 만 풀었으나 시간초과 가 났다 이에 dp와 섞어서 풀어야 한다는 힌트를 보게 되었다

			dp[x][y] = dp[x][y] + dfs(x + xidx[i],y + yidx[i]);

dp의 점화식은 이와 같은데 그이유는 나는 내가 다음에 갈수 있는 경로들이 갈수 있는 경로들의 합으로 표현할수 있기 때문이다

 

나는 dp배열을 -1로초기화를 해주었는데 그이유는 방문하지 않았다는 표시를 -1로 하게되었습니다 0은 방문은 했으나 해당 영역을 통해서 경로를 찾을 수 없는 것이라고 결정 하였습니다. 경로를 탐색하러 들어갔을 때 이미 해당 노드를 방문 한적이 있으면 해당 노드를 통해서 방문했던 길의 갯수가 해당 노드의 저장이 되어있기에 해당 노드의 값을 그대로 반환해주었습니다.

#include <iostream>
#include <set>
using namespace std;
int arr[500][500];
int dp[500][500];
int m, n;
int cnt;
int xidx[4] = { 1,0,-1,0 };
int yidx[4] = { 0,1,0,-1 };
bool canGo(int x, int y, int height) {
	if (x >= 0 && x < m && y>=0 && y < n && height > arr[x][y])
		return true;
	else
		return false;
}

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

	dp[x][y] = 0;
	for (int i = 0; i < 4; i++) {
		if (canGo(x + xidx[i], y + yidx[i], arr[x][y])) {
			dp[x][y] = dp[x][y] + dfs(x + xidx[i],y + yidx[i]);
		}
	}
	return dp[x][y];
}
int main() {
	cin >> m >> n;
	for (int i = 0; i < m; i++) {
		for (int j = 0; j < n; j++) {
			cin >> arr[i][j];
			dp[i][j] = -1;
		}
	}
	cout << dfs(0, 0);
}

전체 로직은 위와 같다