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

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

1. 경로의 개수를 구하는 문제 -> DP일 것으로 예상
2. 각 지점을 거쳐가며 탐색 -> DFS, BFS 예상
   2-1. 목적지까지 도달해야 경우의 수에 포함되므로 DFS로 예상

위의 사고방식을 가졌으나, DFS만으로 경로를 충분히 탐색할 수 있다고 오인하여 시간 초과가 나오는 결과를 확인함.

1번 시간 초과 오답

#include<iostream>
#include<queue>
using namespace std;
#define p pair<int, int>
#define MAX 501

int area[MAX][MAX];
int n, m, answer = 0;
int dx[]{ 0,1,0,-1 };
int dy[]{ 1,0,-1,0 };

void input() {
	cin >> m >> n;
	for (int i = 0; i < m; ++i) {
		for (int j = 0; j < n; ++j) {
			cin >> area[i][j];
		}
	}
}

void solution() {
	queue<p> q;
	q.push({ 0,0 });
	while (!q.empty()) {
		auto curPos = q.front(); q.pop();
		int curHeight = area[curPos.first][curPos.second];
		for (int dir = 0; dir < 4; ++dir) {
			int nx = curPos.first + dx[dir];
			int ny = curPos.second + dy[dir];
			if (nx < 0 || ny < 0 || nx >= m || ny >= n) continue;
			if (area[nx][ny] >= area[curPos.first][curPos.second]) continue;
			if (nx == m - 1 && ny == n - 1) {
				++answer;
				continue;
			}
			q.push({ nx,ny });
		}
	}
	cout << answer;
}

int main() {
	cin.tie(0), cout.tie(0), ios_base::sync_with_stdio(0);
	input();
	solution();
	return 0;
}

따라서 위의 1번 조건도 다시 생각하여 DP + DFS 방법을 사용함. DFS로 탐색을 하며 각 결과값을 DP배열에 추가하는 방식으로 구현하여 정답을 확인

2번 정답

#include<iostream>
using namespace std;

#define MAX 500
int area[MAX][MAX];
int dp[MAX][MAX];
int n, m, answer = 0;
int dx[]{ 0,1,0,-1 };
int dy[]{ 1,0,-1,0 };

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

int dfs(int x, int y) {
	if (x == m - 1 && y == n - 1) return 1;
	if (dp[x][y] != -1) return dp[x][y];
	dp[x][y] = 0;
	for (int dir = 0; dir < 4; ++dir) {
		int nx = x + dx[dir];
		int ny = y + dy[dir];
		if (nx < 0 || ny < 0 || nx >= m || ny >= n) continue;
		if (area[nx][ny] >= area[x][y]) continue;
		dp[x][y] += dfs(nx,ny);
	}
	return dp[x][y];
}

void solution() {
	cout << dfs(0, 0);
}

int main() {
	cin.tie(0), cout.tie(0), ios_base::sync_with_stdio(0);
	input();
	solution();
	return 0;
}