[백준][C++] 1520번: 내리막 길

 

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

1520번: 내리막 길

 

항상 내리막 길로만 이동하는 경로의 개수를 구하는 문제이다.

 

가장 먼저 그래프 탐색으로 dfs가 떠올랐다. 풀이 로직으로는

1. (0,0)에서 시작

2. 인접한 좌표들을 돌며 더 낮은 높이로 이동

3. (M-1,N-1)에 도달하면 경로 개수+1

 

비교적 쉬운 문제였다 생각했으나 시간 초과가 나왔다.

 

 

 

아무래도 최악의 경우 경로의 개수가 10억이므로 재귀 함수로 풀었을 때 시간 초과가 나온 것 같다.

 

그래서 (i,j)에서 목적지까지 내리막 길 경로의 개수를 저장해가며 풀면 어떨까해서 동적프로그래밍 방법을 사용했다.

DP하면 점화식 찾기이므로 그림을 그려가며 규칙을 찾아갔다.

 

DP[i][j] : (i,j)에서 목적지까지 내리막길로만 이동할 수 있는 경로의 개수

핵심 풀이 로직으로는

1. DP배열을 모두 -1로 초기화(아직 방문 하지 않았다는 걸 의미)

2. 처음 방문했다면 인접한 좌표들을 탐색해 내리막 길 경로 개수를 저장한다.

3. 저장된 내리막 길 경로 개수가 있다면 바로 반환

 

 

#include <iostream>

using namespace std;

int M, N;
int map[501][501];
int dp[501][501];
// 상 하 좌 우
int dx[4] = {-1, 1, 0, 0};
int dy[4] = {0, 0, -1, 1}; 

int dfs(int x, int y) {
	if(x==M-1 && y==N-1) {
		return 1;
	}
	
	// 2.(x,y)에서 목적지까지 내리막으로만 갈 수 있는 경로 개수가 저장되어 있지 않다면(처음 방문) 
	if(dp[x][y] == -1) {
		dp[x][y] = 0;
		// 2.인접한 좌표로 경로 탐색
		for(int i=0; i<4; i++) {
			int next_x = x + dx[i];
			int next_y = y + dy[i];
			// 좌표 유효 검사
			if(next_x<0 || next_x>=M || next_y<0 || next_y>=N) continue;
			// 인접한 좌표가 내리막일 경우
			if(map[next_x][next_y] < map[x][y]) {
				dp[x][y] += dfs(next_x, next_y);
			}
		}
	}
	// 3.저장된 경로 개수가 있다면 반환 
	return dp[x][y];
}

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