[BAE/<JOON> 문제풀이] 1520. 내리막길 (DP.032)

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

1520번: 내리막 길

어려운 문제는 dfs가 항상 섞여들어가는 것 같다. 

 

이 문제는 다른 블로그의 풀이를 참고하여 풀었다.

 

일단 점화식 도출까지는 간단하게 생각해 낼 수 있다.

 

경찰차와 비슷하게 bottom-up 방식으로 호출을 하다가 이미 값을 가지고 있는 노드를 탐색하면 해당 값을 반환해가며 

 

합을 구하내가는 방식이다.

 

하지만 제출을 하는데 모두 오답이 나왔다. 아무리 찾아봐도 알 수 가 없어서 풀이와 내 코드를 비교해보는데

 

가장 큰 차이점은 내 코드는 dp배열 0인 상태에서 시작하여 0 초과값을 만나면 방문 상태로 판정하여 값을 가져오고

 

대부분의 풀이들은 -1로 초기화를 한 후, -1이 아닌 값을 만나면 방문 상태로 판정한다는 점이었다.

 

풀이를 처음 봤을 때도 나는 저 부분은 상관이 없다고 생각하다가 계속 안되니까 코드를 고친거였다.

 

곰곰히 생각해보니, 이 문제에서는 막다른 길이 있다.

 

내리막길로 특정 지점에 갔을 때 더 이상 갈 수 있는 공간이 없을 거라는 생각을 하지 않았다. 

 

막다른 공간에 들어가면 갈 수 있는 경우가 0이므로 0으로 초기화를 하고 다른 탐색을 하는데,

 

해당 막다른 공간이 재탐색 되었을 때 미방문 상태로 판정을 하고 계속 탐색을 하게 되어 시간 초과가 발생하는 것이었다.

 

앞으로는 메모이제이션 할 때 그냥 무조건 미방문/방문 상태값을 정해두고 코딩을 해야겠다.

 

 

#include <iostream>
#include <vector>
#include <queue>

using namespace std;

int mvx[5] = { 0, -1, 0, 1, 0 };
int mvy[5] = { 0, 0, -1, 0, 1 };

vector<vector<unsigned long long>> arr, dp, dpr;
int n, m;

unsigned long long r(int x, int y) {	
	//if (x == 1 && y == 1) return 1;
	if (dp[x][y] != -1) return dp[x][y];
	dp[x][y] = 0;
	for (int i = 1; i <= 4; i++) {
		int mx = x + mvx[i];
		int my = y + mvy[i];
		if (mx < 1 || mx > n || my < 1 || my > m || arr[x][y] >= arr[mx][my]) continue;
		dp[x][y] += r(mx, my);
	}
	return dp[x][y];
}

int main() {
	struct node {
		int x, y, c;
	};
	cin >> n >> m;

	queue<node> q;

	arr.resize(n + 2);
	dp.resize(n + 2);
	dpr.resize(n + 2);
	for (int i = 1; i <= n; i++) {
		arr[i].resize(m + 2);
		dp[i].resize(m + 2);
		dpr[i].resize(m + 2);
		for (int j = 1; j <= m; j++) {
			cin >> arr[i][j];
		}
	}
	
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= m; j++) {
			dp[i][j] = -1;
		}
	}

	dp[1][1] = 1;

	cout << r(n, m) << endl;

	/*for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= m; j++) {
			cout << dp[i][j] << " ";
		}
		cout << "\n";
	}*/

	return 0;
}