[BAEKJOON 1520번] (C++) 내리막 길

문제 링크

1520번: 내리막 길

 

• map[m][n] 위치로 이동하기까지의 이동 경로의 수를 구하기 위해 임의의 위치에서 m, n까지 이동경로의 개수를 dp테이블을 통해 계산한다.
• 임의의 x, y에 대한 dp[x][y]는 dp[x+1][y]+dp[x][y+1]+dp[x-1][y]+dp[x][y-1]과 같다.
• 다만 이미 dp가 초기값이 아닌 경우 혹은 범위를 벗어난 경우는 예외로 한다.

 

단순히 dfs만을 사용하여 위 문제를 해결할 경우 모든 경우의 수에 대해 실행하였을 때 

4방향으로 칸을 이동하고 최대범위가500*500이므로

4^(500*500) 개의 경우의 수를 실행하게 됨으로 인해 시간초과로 해결 할 수 없다.

 

 

코드

#include<iostream>
#include<cstring>

using namespace std;

int M, N;
int map[500][500]; //지도 내 높이 저장
int dp[500][500]; //해당 지점에서의 이동 경로 저장
int xi[4] = { 1,0,-1,0 }; //좌 , 우
int yi[4] = { 0, 1, 0, -1 }; // 하,  상 

int DFS(int m, int n) {

	//해당 지점이 목표 지점인 경우 탐색 종료
	if (m == M-1 && n == N-1) {
		return 1;
	}
	//해당 지점이 이미 탐색이 진행된 경우 탐색 종료
	if (dp[m][n]!=-1) {
		return dp[m][n];
	}

	//현재 방문한 지점을 -1-> 0으로 초기화
	dp[m][n] = 0;
	//해당 지점에서 상 하 좌 우 이동을 통해 현재 지점까지의 경로 탐색
	for (int i = 0; i < 4; i++)
	{
		if (m + xi[i] >= 0 && m + xi[i] < M && n+ yi[i]>=0 && n + yi[i] < N)
		{
			if (map[m][n] > map[m + xi[i]][n + yi[i]]) {
				//해당 지점까지의 이동 경로의 수는 다음 이동 경로의 DFS결과의 합으로 저장
				dp[m][n]+=DFS(m + xi[i], n + yi[i]);
			}
		}
	}
	return dp[m][n];

}

int main()
{
	cin >> M >> N;
	int tmp=0;
	for (int i = 0; i < M; i++){
		for (int j = 0; j < N; j++){
			cin >> tmp;
			map[i][j] = tmp;
		}
	}
	memset(dp, -1, sizeof(dp));

	cout << DFS(0, 0) << endl;

	return 0;
}

결과