1520 내리막길

DFS형식의 완전탐색으로 접근했더니, 시간초과가 난 문제다.

어떤식으로 접근해야할 지 고민한 결과 다이나믹 프로그래밍으로 접근해야한단 결론을 내렸다.

그렇다면 어떻게 다이나믹 프로그래밍을 적용해야 할까

문제를 자세히 살펴보면, 중복된 부분문제들이 있는걸 알 수 있다.

예시로 올라온 그림을 살펴보자

첫 번째 예시에서 15가 적힌 칸에 이미 방문하여 목표지점에 도달했기 때문에 두 번째, 세 번째 예시에서 해당 칸에 도달하면 더 이상 탐색하지 않아도 된다.

또한 두 번째 예시에서 20이 적힌 칸을 이미 방문하여 목표지점에 도달했기 때문에 세 번째 예시에서도 더 이상 탐색하지 않아도 된다.

즉, 중복된 부분문제라는 소리다.

 

이러한 중복 부분문제를 다시 계산하는걸 피하기 위해 좋은 기법이 있는데, 메모이제이션이라는 기법이다.

미리 계산해둔 값을 저장해두고, 다음번에 전에 계산해둔 값을 필요로 할 때 바로 사용할 수 있다.

상태 공간 트리 형태로 그려서 생각해보면 이해에 도움이 될 것이다.

 

내가 구현한 방식은 시작점을 기준으로 DFS를 돌려서, 이미 탐색한 칸이 나오면 해당 경로는 도달 가능한 경로로 보고, 경우의 수를 +1 해준다. 탐색하지 않은 칸이 나오면 0으로 초기화 후 다시 DFS를 돌린다.

 

정답코드

#include <iostream>
using namespace std;
int N, M;
#define MAX_SIZE 500
int m[MAX_SIZE][MAX_SIZE];
int dp[MAX_SIZE][MAX_SIZE];
int dirRow[] = { 1, 0, -1, 0 };
int dirCol[] = { 0, 1, 0, -1 };
int dfs(int row, int col)
{
	//기저사례
	if (row == N - 1 && col == M - 1)
		return 1;

	//방문하지 않은 탐색 경로
	if (dp[row][col] == -1) {
		dp[row][col] = 0; //방문처리
		int nr, nc;
		for (int i = 0; i < 4; i++) {
			nr = row + dirRow[i];
			nc = col + dirCol[i];
			if (nr < 0 || nc < 0 || nr >= N || nc >= M)
				continue;
			//다음 칸이 현재 칸보다 작다면, 탐색
			if (m[row][col] > m[nr][nc]) 
				//중복문제를 방지하기 위해 dfs로 탐색
				dp[row][col] += dfs(nr, nc); 
		}
	}
	//다음 칸이 이미 방문한 칸이라면, 더 이상 탐색하지 않고 경우의 수를 +1 한다.
	return dp[row][col];
}
int main()
{
	scanf("%d %d", &N, &M);
	for (int i = 0; i < N; i++)
		for (int j = 0; j < M; j++) {
			scanf("%d", &m[i][j]);
			dp[i][j] = -1;
		}
	printf("%d\n", dfs(0, 0));
	return 0;
}