백준 1520 내리막길

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

1520번: 내리막 길

한 사람이 0,0에서 오른쪽 제일 밑 끝점으로 이동하는 방법의 개수를 구하는 것이다. 특이하게 이동하는 사람은 현재의 위치에서 더 가중치가 낮은 곳으로만 이동할 수 있다. 문제를 처음보면 어 그래프 방법론을 사용해서 풀면되는거 아닌가 하겠지만 여기서 map의 크기가 500임으로  500 * 500 * 4라는 계산 연산으로 시간초과가 발생한다.

 

그래서 dfs랑 dp랑을 조합하여 문제를 해결해야한다. 그래서 이전에 방문한적이 있다면 그대로 값을 반환하고 탐색을 안함으로써 시간 단축을 한다. 그래서 마지막 점에 돌아간 다음 stack을 빠져나오며 방문한 수를 반환하며 해당 위치에 더한다. 

 

그리고 dp의 값을 초기에 -1로 설정해준다. 초기 설정을 0으로 해주면 안되는 이유가 -1과 0과 같거나 큰 값은 방문 안함 방문 했음이다. 만약 전부 0으로 판단이 되면 완전 탐색이되어 시간초과가 발생할 것이다. 

 

#include <cstdio>
#include <string.h>

int M, N;
int map[502][502];
int dp[502][502];

int xPos[4] = {-1, 0, 1, 0};
int yPos[4] = {0, -1, 0, 1};

void input();
int dfsDP(int y, int x);

int main(){
	input();
	printf("%d", dfsDP(0, 0));
}

void input(){
	scanf("%d %d", &M, &N);

	for(int y = 0; y < M; y++)
		for(int x = 0; x < N; x++)
			scanf("%d", &map[y][x]);
	memset(dp, -1, sizeof(dp));
}

int dfsDP(int y, int x){
	if(dp[y][x] != -1)
		return dp[y][x];
	if(y == M-1 && x == N-1)
		return 1;

	if(dp[y][x] == -1){
		dp[y][x] = 0;
		for(int i = 0; i < 4; i++){
			int ay = y + yPos[i];
			int ax = x + xPos[i];
			if(ay >= 0 && ax >= 0 && ay <= M-1 && ax <= N-1 && map[y][x] > map[ay][ax]){
				dp[y][x] += dfsDP(ay, ax);
			}
		}
	}
	return dp[y][x];
}