백준) 1937 욕심쟁이 판다

1937. 욕심쟁이 판다

문제

n*n의 크기의 대나무 숲이 있다. 욕심쟁이 판다는 어떤 지역에서 대나무를 먹기 시작한다. 그리고 그 곳의 대나무를 다 먹어 치우면 상, 하, 좌, 우 중 한 곳으로 이동을 한다. 그리고 또 그곳에서 대나무를 먹는다. 그런데 단 조건이 있다. 이 판다는 매우 욕심이 많아서 대나무를 먹고 자리를 옮기면 그 옮긴 지역에 그 전 지역보다 대나무가 많이 있어야 한다. 만약에 그런 지점이 없으면 이 판다는 불만을 가지고 단식 투쟁을 하다가 죽게 된다(-_-)

이 판다의 사육사는 이런 판다를 대나무 숲에 풀어 놓아야 하는데, 어떤 지점에 처음에 풀어 놓아야 하고, 어떤 곳으로 이동을 시켜야 둘 다 소중한 생명이지만 판다가 최대한 오래 살 수 있는지 고민에 빠져 있다. 우리의 임무는 이 사육사를 도와주는 것이다. n*n 크기의 대나무 숲이 주어져 있을 때, 이 판다가 최대한 오래 살려면 어떤 경로를 통하여 움직여야 하는지 구하여라.

입력

첫째 줄에 대나무 숲의 크기 n(1<=n<=500)이 주어진다. 그리고 둘째 줄부터 1+n번째 줄 까지 대나무 숲의 정보가 주어진다. 대나무 숲의 정보는 공백을 사이로 두고 각 지역의 대나무의 양이 정수 값으로 주어진다. 대나무의 양은 1,000,000보다 작거나 같은 자연수이다.

출력

첫째 줄에는 판다가 최대한 살 수 있는 일수(K)를 출력한다.

예제 입력 

4
14 9 12 10
1 11 5 4
7 15 2 13
6 3 16 8

예제 출력 

4

1. 접근

이차원 배열이 주어지고, 팬더는 아무 지점에서나 시작할 수 있다. 팬더의 이동은 상하좌우의 배열값에 따라 가능한데, 이웃의 배열값이 현재값보다 클 경우에 이동할 수 있다. 모든 이웃지점으로 이동할 수 없다면 팬더는 죽는다!

이러한 조건하에, 팬더가 최대한 오래 살 수 있는 일수는 얼마일까?

= 팬더가 최대한 오래 이동할 수 있는 경우는 무엇일까?

직관적으로 모든 지점에 대해 DFS를 돌려보고 최대값을 구할 수 있겠다.

하지만 한 지점 당 DFS는 N^2 걸리고, 지점은 N^2 개니까 최악 N ^ 4 걸릴 수 있다.

어떻게 최적화시켜야 할까?

2. 풀이

분명히 중복해서 계산하는 과정이 있다. 한 지점은 분명 여러번 방문될 것이며, 그 지점의 정보는 변하지 않는다.(그 지점을 방문했을 때 몇일이나 더 살 수 있는지는 변하지 않는다.)

따라서 메모이제이션과 또이나믹 프로그래밍을 써야한다.

이제 배열을 정의해보자.

DP[x][y] = 현재 내 위치가 x, y 일 때 앞으로 몇일이나 살 수 있는지 정보를 저장.

그러면 당연히 모든 이웃으로 이동이 불가능하면, 그 날만 살고 죽을테니 그런 DP[x][y] = 1 이다.

함수 func(int x, int y) = DP[x][y]를 계산해서 리턴해주는 기능을 하게 하고, 기저사례를 구분해보자.

당연히 기저사례는 위와같은 이동이 불가능한 지점이다.

아니라면, 이동가능한 지점마다 함수를 호출해주면 된다.

그런 지점으로 이동하면 하루를 더 살 수 있을테니, 그런 지점을 xx, yy 라고 하면, func(x, y) = func(xx, yy) + 1 이다.

3. 코드

#include <stdio.h>
#include <string.h>
#include <algorithm>
#include <vector>
using namespace std;
 
struct p {
    int xx, yy;
};
 
int n, i, j;
int map[500][500];
int dp[500][500];
int dir[4][2] = { {-1,0},{1,0},{0,-1},{0,1} };
 
int func(int x, int y) {
    vector<p> c; // 갈 수 있는 장소들 저장
    bool all = false; // 다 갈수 없다고 생각
 
    for (int i = 0; i < 4; ++i) {
        int xx = x + dir[i][0];
        int yy = y + dir[i][1];
 
        if (xx < 0 || yy < 0 || xx >= n || yy >= n)
            continue;
 
        if (map[xx][yy] > map[x][y]) { // 갈 수 있으면 기저사례가 아님
            all = true;
            c.push_back({ xx,yy });
        }
    }
 
    if (all == false)
        return 1;
 
    int& ref = dp[x][y];
    if (ref != 0)
        return ref;
 
    for (auto pp : c)
        if (map[pp.xx][pp.yy] > map[x][y])
            ref = max(ref, func(pp.xx, pp.yy) + 1);
 
    return ref;
}
 
int main() {
    scanf("%d", &n);
 
    for (i = 0; i < n; ++i)
        for (j = 0; j < n; ++j)
            scanf("%d", &map[i][j]);
 
    int ans = 0;
    for (i = 0; i < n; ++i)
        for (j = 0; j < n; ++j)
            ans = max(ans, func(i, j));
        
    printf("%d", ans);
 
    return 0;
}