[BOJ-1937]욕심쟁이판다

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

욕심쟁이판다

n*n 정방행렬 크기의 숲이 있고,

각 (row, col) 위치의 숲마다 판다가 먹을 수 있는 대나무 수가 주어진다. 

그 위치에 있는 경우 하루만에 대나무를 다 쳐먹음.

이 판다는 꼭 이전에 먹었던 위치에 대나무 수보다

많은 대나무가 있는 위치로 가야한다.

적은 수와 동일한 대나무 수가 있는 곳에 가면 뒤진다.....

그래서 이 판다가 가장 오래살 수 있는 날을 구해야한다. 

각 시작한 위치마다 더 오래살 수 있는 날이 다르기 때문에 이를 구한다. 

[입력]

n

a[0][0] a[0][1] .... a[0][n-1]

...

a[n-1][0] ... a[n-1][n-1]

숲 크기 n 이 주어지고 (n*n)

숲에 대한 대나무 수의 정보가 주어진다.

[출력]

판다가 오래살 수 있는 일수를 구한다. 

[접근방법]

이전에도 풀었던 문제인데 이전에는 정말 많이 틀렸었다.

이전 코드를 보니 BFS 로 하려고 했는데 36% 에서 시간초과를 여러번 받았나보다. 

계산된 값을 계속해서 계산하려고 하니 그랬었고,

일단 문제 분류가 DP 인데

사실 상 DFS 로 풀긴하고 가지치기를 해서 풀었다. 

조건에서 판다는 

0) 숲 ( n * n ) 을 벗어 날 수 없다. 

1) 더 많은 대나무가 있는 곳으로 이동해야한다. 

그럼 이 조건으로 움직을 수 있는지 없는 지를 판단한다. 

+) 현재 위치에서 살 수 있는 최대일수 보다 - 이동할 곳의 살 수 있는 최대일수가 클 때 이동하지 못한다. (가지치기)

위 3가지의 경우가 될 경우 판다는 이동할 수 있다. 

처음엔 기록되지 않은 상태에서 DFS 로 살 수 있는 최대 일 수를 memo[r][c] 에 기록한다.

모든 숲이 시작점이 되어 모든 경우를 찾는다. 

그리고 이중 memo[r][c] 의 최대값이 정답이 된다.

#include<cstdio>
#include<queue>
#define din1(a) scanf("%d", &a)
using namespace std;
 
const int M = 505;
int imap[M][M];
int memo[M][M];
int dr[] = { 0,0,-1,1 };
int dc[] = { 1,-1,0,0 };
int n;
int ans;
 
int max2(int a, int b) {
    return (a > b) ? a : b;
}
 
bool is_move(int hr, int hc, int tr, int tc) {
    if (!(0 <= tr && tr < n && 0 <= tc && tc < n)) return false;
    if (imap[hr][hc] >= imap[tr][tc]) return false;
    if (memo[hr][hc] < memo[tr][tc]) return false;
    return true;
}
 
void dfs(int row, int col, int day) {
    if (memo[row][col] < day) memo[row][col] = day, ans = max2(ans, day);
    else if(memo[row][col] > day) return;
    for (int i = 0; i < 4; i++) {
        int tr = row + dr[i];
        int tc = col + dc[i];
        if (is_move(row, col, tr, tc)) {
            memo[row][col] = day;
            dfs(tr, tc, day+1);
        }
    }
}
 
int main() {
    din1(n);
    for (int r = 0; r < n; r++) {
        for (int c = 0; c < n; c++) din1(imap[r][c]);
    }
    
    for (int r = 0; r < n; r++) {
        for (int c = 0; c < n; c++) dfs(r, c, 1);
    }
    printf("%d", ans);
    return 0;
}