[백준] 1520 - 내리막 길

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

1520번: 내리막 길

 

알고리즘 방식

DFS를 활용한 DP 방식이였다.

코드를 보면 DP배열을 모두 -1로 초기화하는 부분이 있는데, 이 부분이 핵심이다.

• 먼저 dp배열의 값은 해당 위치에서 도착지점에 도달할 수 있는 경우의 수이다.
• 따라서 특정 위치가 0이라면, 해당 위치에서 도착지점에 도달할 수 있는 경우는 0이라는 의미다.
  이는 즉, 해당 위치에서 도착 지점에 도달할 수 있는지를 이미 탐색을 했다라는 의미도 된다.
• 따라서 dp배열은 모두 -1로 초기화하여, 특정 위치에서 DFS 탐색을 시작할 때,
  해당 위치를 0으로 초기화 후 DFS 탐색을 시작하여 값을 매긴다.

 

소스코드

#include <iostream>
#include <algorithm>

using namespace std;

int board[501][501];
int dp[501][501];

int N, M, answer;
int dx[4] = { 0, 0, 1, -1 };
int dy[4] = { 1, -1, 0, 0 };

int dfs(int curX, int curY) {
	if (curX == M - 1 && curY == N - 1) {
		return 1;
	}

	if (dp[curX][curY] != -1)
		return dp[curX][curY];

	dp[curX][curY] = 0;
	for (int dir = 0; dir < 4; dir++) {
		int nx = curX + dx[dir];
		int ny = curY + dy[dir];

		if (nx < 0 || ny < 0 || nx >= M || ny >= N) {
			continue;
		}

		if (board[nx][ny] < board[curX][curY]) {
			dp[curX][curY] += dfs(nx, ny);
		}
	}
	return dp[curX][curY];
}

int main(void) {
	ios::sync_with_stdio(false);
	cin.tie(NULL);

	cin >> M >> N;
	for (int i = 0; i < M; i++) {
		for (int j = 0; j < N; j++) {
			cin >> board[i][j];
		}
	}
	fill(&dp[0][0], &dp[500][501], -1);
	cout << dfs(0, 0);
}