백준 1937 욕심쟁이 판다 (C++)

1937번: 욕심쟁이 판다

처음 이 문제를 봤을 때 지도 위에서 상하좌우로 이동을 한다는 것을 보고 BFS라고 판단하고 알고리즘을 구상했다. 그러나 칸마다 최대 이동 개수가 정해져있으며, 단순한 BFS로는 시간 초과가 난다는 점에서 dp를 구상해야겠다고 판단했다. 우선 BFS를 사용하면 주변 칸을 먼저 탐색하기에 비효율적이어서 DFS를 이용했다. 모든 점에서 DFS를 돌려보면서 dp를 채웠고 그 중 최장 거리를 구했다.
섣부르게 BFS로 판단하여 시간이 오래걸렸다. 문제를 더 자세히 살펴보자.

#include <iostream>
#include <algorithm>

using namespace std;

int n, res = 0;
int A[501][501];
int dp[501][501];
int dy[4] = { -1,1,0,0 };
int dx[4] = { 0,0,-1,1 };

void dfs(int y, int x) {
	if (dp[y][x]) return;

	int count = 0;

	for (int i = 0; i < 4; i++) {
		int ny = y + dy[i];
		int nx = x + dx[i];

		if (ny < 0 || nx < 0 || ny >= n || nx >= n) continue;
		if (A[ny][nx] <= A[y][x]) continue;

		dfs(ny, nx);

		count = max(count, dp[ny][nx]);
	}

	dp[y][x] = count + 1;
}

void solution() {
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			dfs(i, j);

			res = max(res, dp[i][j]);
		}
	}

	cout << res;
}

int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL); cout.tie(NULL);

	cin >> n;
;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			cin >> A[i][j];
		}
	}

	solution();
	
	return 0;
}