[c++] 백준 - 1520 내리막길 (DFS + DP)

1. 문제

2. 입출력 및 예제

3. 문제 해설

상하좌우가모두 탐색이 가능하다. 그리고 제약조건이 존재한다. 바로 현재 위치보다 낮은 수로만 이동할 수 있다는 점이다.

기본적으로는 dfs탐색을 해야할 거 같았다. 결국 자신의 네 방향 중 자신보다 낮은 수가 존재한다면 이동 횟수는 상관없이 이동할 수 있는 것이고 결국 오른쪽 맨 아래 칸에 도달할 수 있는 지에 대한 여부가 중요했기 때문이다. 

 

따라서 나는 상태를 3가지로 나누었다. 

• -1 : 아직 방문하지 않은 곳이다.
• 0 : 방문한 경우이다. 
• 0보다 큰 수  : 현재 지점에서 목적지까지 도달 할 수 있는 경우의 수가 존재하는 곳이다. 

처음에는  이 문제를 백트래킹으로 접근했는데 시간초과가 났다. 물론 4가지 방향 ^ (500 * 500)이 최악의 경우라 당연히 시간초과는 날 수 있을 것이다. 따라서 dfs를 적용하며 dp를 같이 적용했는데

 

백트래킹은 경로를 찾을 수 없는 경우 경우의 수가 남아있는 칸까지 다시 갔던 흔적을 지우면서 돌아와 나머지 경우의 수를 탐색하는 반면 이미 방문한 노드라면 이 지점서부터 dfs를 다시 돌려 오른쪽 아래에 도달할 수 있는 경우의 수를 memoization해주면서 왔다. 따라서 한 번 방문한 노드라면 (-1이 아니라면) 다시 돌아갈 필요없이 여기서 dfs를 다시 돌려서 오른쪽 아래에 도달 할 수 있는 지를 찾아주면 되는 것이다. 

 

4. 코드

#pragma warning (disable : 4996)

#include <cstdio>
#include <cstring>
#define MAX 502
using namespace std;

int N, M;
int maps[MAX][MAX];
int visited[MAX][MAX];
int dy[4] = { 0,1,0,-1 };
int dx[4] = { -1,0,1,0 };
int ans;
int dfs(int y, int x) {
	if (y == N - 1 && x == M - 1)return 1; // 목적지에 도착하는 경우 1을 반환
	if (visited[y][x] == -1) { // 방문하지 않았다면
		visited[y][x] = 0; // 방문 표시 
		for (int i = 0; i < 4; i++) {
			int ny = y + dy[i];
			int nx = x + dx[i];
			if (ny < 0 || nx < 0 || ny >= N || nx >= M) continue;
			if (maps[ny][nx] >= maps[y][x]) continue;
			visited[y][x] += dfs(ny, nx);
			
			//visited[ny][nx] = 0; 백트래킹은 시간초과가 난다.
		
		}
	}
	return visited[y][x]; // 현재의 값을 리턴한다. 현재 경로까지 올 수 있는 경로의 수 
}
void input() {
	memset(visited, -1, sizeof(visited)); // visited배열 초기화
	scanf("%d %d", &N, &M);
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < M; j++) {
			scanf("%d", &maps[i][j]);
		}
	}
}
int main() {
	input();
	ans = dfs(0, 0);
	printf("%d\n", ans);
	return 0;
}