[G3] 백준 1520번 내리막 길 C++ 다이나믹 프로그래밍, 깊이 우선 탐색

리뷰

 

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

DFS + DP를 활용하여 푸는 문제, 그냥 DFS로 접근했다가 시간 초과를 계속 받았다.

 

 

전역 변수

• n, m : 맵의 세로/가로 길이를 저장할 변수
• lst : 맵 정보를 저장할 2차원 배열
• v : 방문 처리를 위한 2차원 배열
• dp : 우하단으로 이동 가능한 경로의 개수를 저장할 2차원 배열
• dx, dy : 4방향 탐색을 위한 방향 배열

 

함수

1. dfs

int dfs(int x, int y)

 

너비 우선 탐색 + DP를 통해 우하단으로 이동 가능한 모든 경로의 개수를 구하는 함수

1. 첫 번째 기저 조건으로 맵의 우하단에 도달하였다면 1을 리턴해 준다.
2. 두 번째 기저 조건으로 이미 dp값이 저장되어 있다면 해당 값을 리턴해 준다.
3. 현재 좌표의 dp값을 0으로 초기화 하고, 변수 cur에 맵 상에서의 값을 저장해 준다.
4. 4방향 탐색을 진행하며 이동할 위치가 맵의 범위 안이고, 방문하지 않았고, 현재 값보다 작다면 이동을 진행해 준다.
5. 이동 후엔 방문체크 후 현재 dp값에 이동 위치를 재귀를 진행한 값을 더해준다.
6. 재귀를 빠져나오며 방문 체크를 다시 풀어준다.
7. 탐색을 마친 후엔 현재 dp값에 저장된 값을 리턴해 준다.

 

문제풀이

1. n, m값을 입력 받고, n * m크기의 맵 정보를 lst에 입력 받아준다, 이 때 dp값을 모두 -1로 변경해 준다.
2. dfs함수의 초기 위치값 0, 0을 매개변수로 전달하여 호출하고 리턴 받은 값을 출력해 준다.

 

트러블 슈팅

1. DFS내에서 우하단에 방문 불가한 좌표를 체크해 가지 않도록 가지치기 했으나 시간 초과가 출력되었다.
2. Top-Down형식의 DP를 사용하여 적용하였더니 AC를 받았다.

 

참고 사항

• Bottom-Up방식을 사용할 경우 재귀 및 방문처리를 사용하지 않아도 된다.

 

정답 코드

#include<iostream>
using namespace std;

int n, m;
int lst[500][500];
bool v[500][500];
int dp[500][500];
int dx[] = { 0, 0, 1, -1 };
int dy[] = { 1, -1, 0, 0 };

int dfs(int x, int y) {
	if (x == n - 1 && y == m - 1) return 1;
	if (dp[x][y] != -1) return dp[x][y];

	dp[x][y] = 0;
	int cur = lst[x][y];

	for (int i = 0; i < 4; ++i) {
		int nx = x + dx[i], ny = y + dy[i];
		if (0 <= nx && nx < n && 0 <= ny && ny < m && !v[nx][ny] && lst[nx][ny] < cur) {
			v[nx][ny] = true;
			dp[x][y] += dfs(nx, ny);
			v[nx][ny] = false;
		}
	}
	return dp[x][y];
}

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);

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

	cout << dfs(0, 0);
}