n x n 크기의 대나무 숲에서 판다는 상, 하, 좌, 우로 이동하며 대나무를 먹는다.
이때, 이동한 칸은 그 전 지역보다 대나무가 많이 있어야 한다.
판다가 이동할 수 있는 칸의 수의 최댓값을 구하자.
예시 이미지 설명 추가
문제를 읽고 가장 쉽게 떠올릴 수 있는 방법은 dfs를 통한 완전 탐색으로, 대나무 숲 전체를 방문하며 경로를 탐색하는 것이다. 그러나 n의 크기는 최대 500이고 2초의 시간제한이 있으므로, 이 방법으로는 해결할 수 없다.
물론 판다가 이동할 칸 수의 최댓값을 저장해야하므로 dfs를 재귀적으로 호출해야한다. 키 포인트는 dfs와 함께 dp를 사용하는 것이다. dp를 추가하면 반복되는 계산의 결과값을 이후의 계산에 이용할 수 있어, 탐색 시간을 줄일 수 있다.
https://github.com/meraki6512/Algorithm/blob/master/AlgorithmProject1/1937.cpp
코드 설명 추가
#include <iostream>
#include <algorithm>
#include <vector>
#define INF 505
using namespace std;
int N;
const int dx[4] = {0, 0, 1, -1};
const int dy[4] = {-1, 1, 0, 0};
int dp[INF][INF];
int v[INF][INF];
int main(void) {
cin >> N;
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
cin >> v[i][j];
}
}
int max_len = 0;
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
max_len = max(max_len, dfs(i, j));
}
}
printf("%d", max_len);
}
int dfs(int x, int y) {
if(dp[x][y]) return dp[x][y];
dp[x][y] = 1;
for (int i = 0; i < 4; i++) {
int nx = x + dx[i], ny = y + dy[i];
if (nx < 0 || nx >=N || ny < 0 || ny >=N) continue;
if (v[x][y] >= v[nx][ny]) continue;
dp[x][y] = max(dp[x][y], dfs(nx, ny) + 1);
}
return dp[x][y];
}