[백준] 욕심쟁이 판다_1937

중복 계산을 막기 위해 cache 리스트를 만들어 이미 계산한 값을 저장해둔다. 

어떤 위치에서 판다가 오래 삼을 수 있다는 말은 조건에 맞게 dfs를 타고 갈 수 있는 경로도 길다는 뜻이다. 경로를 맞게 타고 갈 때마다 그 위치에서 또 갈 수 있는 경로를 탐색한다. 만약 어떤 위치에서 갈 수 있는 경로가 아예 없다면 ret은 1인채로 반환이 될 것이고, 이것은 그 위치에서 팬더가 하루밖에 못 산다는 것을 의미한다. 

갈 수 있는 경로가 두 개 더 있는 상태라면?

ret = max(ret,panda(ny, nx)+1);

dfs를 따라 갔을 때 더 갈 수 있는 경로가 있으므로 

ret = max(ret,panda(ny, nx)+1); 가 또 호출된다. 

세번째 실행되는 dfs 함수에서는, 여기서 또 갈 수 있는 경로는 없으므로 panda(ny, nx) 결과 1이 반환된다.  그 결과 두번째 호출문에서는 2를 반환시키고, 맨 처음 호출문에서의 ret 값도 3이 된다. 

 

#include <iostream>
#include <string.h>
#include <algorithm>
using namespace std;
 
int n; 
int boo[500][500];
int cache[500][500];
int dx[4] = { -1, 1, 0, 0 };
int dy[4] = { 0, 0, -1, 1 };
int MAX = 0;
 
 
bool isout(int i, int j) {
    return i < 0 || j < 0 || i >= n || j >= n;
}
//cache : 그 위치에서 팬더가 앞으로 살아남을 수 있는 최대 일수 
int panda(int y, int x) {
    int& ret = cache[y][x];
    if (ret != -1) return ret;
    ret = 1; 
    for (int d = 0; d < 4; d++) {
        int ny = y + dy[d];
        int nx = x + dx[d];
        if (isout(ny, nx)) continue;
        //새로 갈 수 있는 경로까지 끝까지 가면서 그 위치에서 최대로 살아남을 수 있는 일수를 현재 위치에 저장  
        if (boo[y][x] < boo[ny][nx]) {
            ret = max(ret,panda(ny, nx)+1);
        }
    }
    return ret; 
}
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);
    cin >> n;
    memset(cache, -1, sizeof(cache));
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            cin >> boo[i][j];
        }
    }
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            panda(i, j);
        }
    }
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            if (cache[i][j] > MAX) MAX = cache[i][j];
        }
    }
    cout << MAX;
    return 0;
}