[백준] 1520번 내리막 길

DFS와 DP를 사용하여 내리막길로 길을 가다가 만약 방문한 적이 있는 칸이 있다면 끝까지 가지 않고 해당 칸의 DP 값을 더한다.

 

 

DP는 해당 칸에서 목적지까지 갈 수 있는 경우의 수다. -1로 초기화한 이유는 0인 경우는 목적지까지 갈 수 있는 경우의 수가 없는 것이고 -1인 경우는 아직 방문을 안한 경우다.

 

 

(x, y)가 목적지면 1을 리턴하고 방문한 적이 있으면 해당 DP값을 리턴한다. 아직 방문을 하지 않았으면 상, 하, 좌, 우를 보며 지점의 높이가 더 낮으면 해당 지점으로 가서 DP값을 계산하여 이렇게 상, 하, 좌, 우의 갈 수 있는 DP값을 더해준다.

 

 

전체 코드

#include <bits/stdc++.h>

using namespace std;

int dx[] = { -1,0,1,0 };
int dy[] = { 0,-1,0,1 };

vector<vector<int>> board(501, vector<int>(501)); // 지도
vector<vector<int>> DP(501, vector<int>(501, -1)); // (i, j)에서 목적지까지의 경우의 수
int N, M, answer;

int DFS(int x, int y) {
	if (x == N - 1 and y == M - 1)
		return 1;

	// 이미 방문한 적이 있어 경우의 수를 계산을 해놓은 경우
	if (DP[x][y] > -1)
		return DP[x][y];

	// 경우의 수 계산
	DP[x][y] = 0;
	for (int k = 0; k < 4; k++) {
		int xpos = x + dx[k];
		int ypos = y + dy[k];

		if (xpos < 0 or xpos >= N or ypos < 0 or ypos >= M)
			continue;
		if(board[x][y] > board[xpos][ypos])
			DP[x][y] += DFS(xpos, ypos);
	}
	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 >> board[i][j];
		}
	}

	answer = DFS(0, 0);
	cout << DP[0][0];

	return 0;
}