백준 No.1937 [욕심쟁이 판다]

Baekjoon Online Judge No.1937 [욕심쟁이 판다]

---

 문제 

1937번: 욕심쟁이 판다

---

 설명 

  DFS를 활용한 DP문제이다.

 

  land[i][j] array 를 입력되는 대나무 숲에 대한 정보이고,

  dp[i][j] array 를 (i, j) 위치에서 최대로 살 수 있는 일수라고 하자.

 

  백준 사이트에 있는 입력 예시이다. 한 위치를 예로 설명을 해 볼 것이다. 위 경우를 가지고 dp[0][1]의 값을 구하는 과정, 식은 아래와 같다.

 

 

dp[0][1] = max(dp[0][0] + 1, dp[1][1] + 1, dp[0][2] + 1)

  위 식 처럼 현재 위치의 dp의 값은 상하좌우에 해당이 되는 dp값에서 1을 더한 값과 같다. 이 때 위 case 는 주변 land의 값이 모두 현재 land의 값보다 커서 모두 현재 위치의 dp값을 구하는 데 참고를 하였다.

 

  현재 위치의 dp의 값을 구할 땐 상하좌우에 해당이 되는 land의 값이 현재 위치의 land의 값보다 큰 경우에만 dp값을 구하는데 참고를 하게 된다.

 

  그리고 임의의 위치에 대한 dp의 값은 한 번 구해지면 다른 위치의 dp의 값을 구하는 과정에서 접근을 할 때 바로 사용을 할 수 있다. 예를 들어서, 위 dp[0][1]의 값을 구하면서 dp[0][0], dp[0][2], dp[1][1], dp[2][1] 의 값이 모두 구해진다. dp[1][1]의 값은 2로 정의되며, 이는 dp[1][2]의 값을 구할 때 바로 사용이 될 수 있다.

 

  위 경우는 n 의 값이 4인 경우라 모든 위치에 대해서 계속해서 DFS를 통해 값을 구해도 시간이 얼마 걸리지 않지만, n의 값이 많이 큰 경우에는 시간의 소모가 클 것이다. 따라서 임의의 위치에 대한 dp값은 구현된 코드와 같이 한 번 구하면 이후론 더이상의 DFS를 통해 구할 필요가 없게 구현을 해야 한다.

---

 Code 

#include <iostream>
#include <vector>
 
using namespace std;
 
int n;
int land[500][500];
int dp[500][500];
int di[4] = { 1, -1, 0, 0 };
int dj[4] = { 0, 0, 1, -1 };
 
bool isSafe(int x, int y) { //  범위를 넘어가지 않는지 확인
    return x >= 0 && x < n && y >= 0 && y < n;
}
 
int DFS(int i, int j) {
    if (dp[i][j]) return dp[i][j]; 
    dp[i][j] = 1;
 
    for (int d = 0; d < 4; d++) {
        int next_i = i + di[d];
        int next_j = j + dj[d];
 
        if (!isSafe(next_j, next_i)) continue;
        if (land[next_i][next_j] <= land[i][j]) continue;
 
        dp[i][j] = max(dp[i][j], DFS(next_i, next_j) + 1);
    }
 
    return dp[i][j];
}
 
int solve() {
    int ans = 0;
 
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            ans = max(ans, DFS(i, j));
        }
    }
 
    return ans;
}
 
int main() {
    cin >> n;
 
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            cin >> land[i][j];
        }
    }
 
    cout << solve();
}