백준 1520 내리막 길

 

---

(0,0)좌표부터 (n-1,m-1)좌표까지 도달할 수 있는 모든 경로를 찾는 문제다. 

다음 타일의 값이 더 작기만 하면 되는 조건이라 금방 풀 수 있을 거라 생각했다..

 

처음에 그냥 bfs로 풀고 답이 나와서 제출하니 시간초과가 나왔다. 

이 문제를 해결하기 위해서는 위해서는 dfs + dp로 최적화하여 계산한 다음 값을 내야 한다고 한다.. 

(문제는 최단 경로를 찾는 것이 아닌 가능한 모든 경로를 찾는 것이므로 bfs보단 dfs를 사용해 푸는 것이 더 낫다고 한다.!)

 

어떻게 최적화 해야 하는가? 🤔

-> 방문한 길을 다시 방문하지 말야아 한다. 

 

그럼 방문한 길을 어떻게 피하는가?

-> dp배열의 값을 0이 아니라 음수값으로 초기화하고, 탐색한 dp배열 값이 음수인 경우에만 업데이트를 진행한다. 음수가 아닌 경우 다시 계산을 진행하지 않고 저장된 값을 사용한다.

 

---

코드 설명

move 함수는 x,y부터 출발해서 n-1, m-1까지 도달할 수 있는 경로의 수를 반환한다.

먼저 dp[x][y] 저장 값이 -1인 경우 값을 0으로 다시 저장한다.(dp배열의 업데이트는 다음 칸(nx, ny) 높이가 더 낮은 경우 dp[x][y]는 dp[x][y] + move(nx,ny)이다.)

 

1. 만약 도착지점에 도달했다면 1을 반환한다.

2. 한번이라도 방문한 경로라면 다시 탐색하지 않고 dp[x][y]을 반환한다. dp[x][y]에 이미 도착지점까지 도달 가능한 경로의  수가 저장되어있기 때문이다.

3. 만약 다른 지점으로 이동할 수 없는 경우에는 dp[x][y] 에 저장되어있던 0을 그대로 반환한다. 

..

 

상하좌우 모두 갈 수 없는 지점에 도달한 경우 그 좌표의 dp값은 0 이다. dp[x][y]배열을 업데이트하기위해서는 상하좌우에 방문가능한 공간이 있어야하므로 0으로 남게된다. 

오른쪽과 아래쪽으로 이동 가능한 좌표에서는 move(nx,ny)로 아래 방향을 먼저 탐색한 후, 다음 for문을 통해 오른쪽 방향을 확인하게 된다. 방향에 따른 move의 반환값이 누적해 더해지기 때문에 모든 가능한 방향을 찾을 수 있게 된다. 

..

 

따라서 결국 dp[0][0]에는 dfs 탐색을 통해 계산된 도착지점으로 가는 모든 경우의 수가 저장되게 된다.!!

 

 

 

#include<iostream>
#include<vector>

using namespace std;
int n, m;
vector<vector<int>>path;
vector<vector<long long>>dp;
int dx[] = {0,1,0,-1};
int dy[] = {1,0,-1,0};

int move(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;//한번도 안 방문한 경로
	for (int i = 0; i < 4; i++) {
		int nx = dx[i] + x;
		int ny = dy[i] + y;
		if ((nx >= 0 && nx < n) && (ny >= 0 && ny < m)) {
			if ((path[x][y]>path[nx][ny])) {
				dp[x][y] = dp[x][y] + move(nx, ny);
			}
		}
	}
	return dp[x][y];
}



int main() {
	ios::sync_with_stdio(0);

	cin >> n >> m;

	path.resize(n, vector<int>(m, 0));
	dp.resize(n, vector<long long>(m, -1));

	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			cin >> path[i][j];
		}
	}
	if (n == 1 && m == 1) {
		cout << 1;
		return 0;
	}

	move(0,0);

	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			cout << dp[i][j] << " ";
		}
		cout << " \n";
	}
	cout << dp[0][0];
	return 0;
}