[C++] BOJ(백준) 1520 내리막 길

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

1520번: 내리막 길

 

DP와 DFS 문제다.

 

DFS를 통해 경로를 탐색하고, 돌아오는 길에 경우의 수를 저장해 값이 존재하는 경우 더 탐색하지 않는 DP를 이용한다.

DFS의 return 조건은 도착지에 도달 했을 떄, 이미 방문한 적이 있을 때다.

모든 경로의 전체를 탐색하면 당연히 시간초과가 나기 때문에 이미 방문한 적이 있을 경우에는 탐색을 멈춘다.

탐색을 멈추고, 해당 칸에 저장된 값을 현재 칸에 더한다.

그렇게 쭉 더해와서 (1, 1)에는 도착지까지 갈 수 있는 모든 경로가 저장된다.

 

그러나 이 방법을 써도 시간초과가 났는데, 간과한 점이 이미 탐색한 경우는 방문 배열이 0이라는 점이다.

이런 경우에는 방문을 했음에도 방문이 티가 나지 않아 또 탐색하게 된다.

그래서 방문 배열을 -1로 초기화 하고 방문시 0으로, 도착지에 도달하고 왔다면 경우의 수로 저장했다.

 

#include <iostream>
#include <queue>
using namespace std;

int n, m;
int arr[502][502];
int dp[502][502];

int dr[4] = { 0, 0, 1, -1 };
int dc[4] = { 1, -1, 0, 0 };

int dfs(int r, int c) {
	if (r == n && c == m) return 1;
	if (dp[r][c] != -1) return dp[r][c];
	else {
		dp[r][c] = 0;
		for (int i = 0; i < 4; i++) {
			int nr = r + dr[i];
			int nc = c + dc[i];

			if (arr[r][c] <= arr[nr][nc]) continue;

			dp[r][c] += dfs(nr, nc);

		}
	}
	return dp[r][c];
}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL); cout.tie(NULL);

	cin >> n >> m;

	for (int i = 1; i <= n; i++)
		for (int j = 1; j <= m; j++) {
			cin >> arr[i][j];
			dp[i][j] = -1;
		}

	cout << dfs(1, 1);
}

 

 

https://wootool.tistory.com/83

위 블로그를 참고하면 이해가 쉬울 것이다. 그림으로 잘 나타나있다.