내리막 길 (feat. 백준, 1520번)

내리막 길
https://www.acmicpc.net/problem/1520

1520번: 내리막 길

반응형

// woohyeon.kim
// https://www.acmicpc.net/problem/1520
#include <iostream>
using namespace std;
int N, M, arr[501][501], dp[501][501], dx[4], dy[4];
int dfs(int x, int y) {
	if (x == N && y == M)		return 1;
	if (dp[x][y] != -1)			return dp[x][y];
	dp[x][y] = 0;
	for (register int d = 0, nx, ny; d < 4; ++d) {
		nx = x + dx[d], ny = y + dy[d];
		if (1 <= nx && nx <= N && 1 <= ny && ny <= M && arr[x][y] > arr[nx][ny])
			dp[x][y] += dfs(nx, ny);
	}
	return dp[x][y];
}
int main() {
	ios::sync_with_stdio(false), cin.tie(), cout.tie();
	dx[0] = 1, dx[1] = -1, dx[2] = dx[3] = 0;
	dy[0] = dy[1] = 0, dy[2] = 1, dy[3] = -1;
	cin >> N >> M;
	for (register int x = 1, y; x <= N; ++x)
		for (y = 1; y <= M; ++y)
			cin >> arr[x][y], dp[x][y] = -1;
	cout << dfs(1, 1) << endl;
	return 0;
}
// *&)*@*

1. dfs나 bfs나 둘다 풀이가 가능합니다.
2. 요지는 시작점 기준 하나의 방향에 대해서 갈수 있는 모든 경우를 찾고, 이미 갔던 지점을 방문했을 경우, 이전의 값을 그대로 이용한다 라는 것입니다.
3. 왜냐면 (1,1) -> (x,y) 로 갔다고 했을때, (x,y)에서 갈수 있는 모든 경우를 기록하고 추후 (1,1) 에서 다른 방향에 의해 (x,y)가 호출되었다면 남겨진 값을 사용하여 재방문하지 않을 수 있기 때문입니다.