[BOJ 백준 1937번 - 욕심쟁이 판다] 해설

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

1937번: 욕심쟁이 판다

문제 설명

n × n의 크기의 대나무 숲이 있다. 욕심쟁이 판다는 어떤 지역에서 대나무를 먹기 시작한다. 그리고 그 곳의 대나무를 다 먹어 치우면 상, 하, 좌, 우 중 한 곳으로 이동을 한다. 그리고 또 그곳에서 대나무를 먹는다. 그런데 단 조건이 있다. 이 판다는 매우 욕심이 많아서 대나무를 먹고 자리를 옮기면 그 옮긴 지역에 그 전 지역보다 대나무가 많이 있어야 한다.
이 판다의 사육사는 이런 판다를 대나무 숲에 풀어 놓아야 하는데, 어떤 지점에 처음에 풀어 놓아야 하고, 어떤 곳으로 이동을 시켜야 판다가 최대한 많은 칸을 방문할 수 있는지 고민에 빠져 있다. 우리의 임무는 이 사육사를 도와주는 것이다. n × n 크기의 대나무 숲이 주어져 있을 때, 이 판다가 최대한 많은 칸을 이동하려면 어떤 경로를 통하여 움직여야 하는지 구하여라.

문제 요약

n × n 크기의 숲의 각 칸의 대나무 수가 주어져 있다. 판다는 특정 칸에서 시작하고 상하좌우로 움직이며 각 칸의 대나무 수는 오름차순으로 증가해야 한다. 이때 판다가 이동할 수 있는 칸 수의 최대값은?

접근법

이 문제는 간단한 DFS/BFS 문제처럼 보이지만, 탐색중 방문하는 칸에서 중복으로 탐색을 하면 시간초과가 뜬다. 따라서 DP를 섞어서 풀어야 한다. 간단하게 DFS로 탐색하면서, 각 칸에서 이동할 수 있는 칸 수의 최대값을 DP로 계속 갱신해주면 된다. 

 

#include <bits/stdc++.h>
using namespace std;
int n, q[600][600], w[600][600], m, x[]={0,0,-1,1}, y[]={1,-1,0,0};
void bfs(int a, int b){
    int k = 0;
    for(int j=0;j<4;j++){
        if(a+x[j]==0 || a+x[j]==n+1 || b+y[j]==0 || b+y[j]==n+1) continue;
        if(q[a+x[j]][b+y[j]] < q[a][b]){
            k = 1;
            if(w[a+x[j]][b+y[j]] != 0) w[a][b] = max(w[a+x[j]][b+y[j]]+1, w[a][b]);
            else{
                bfs(a+x[j], b+y[j]);
                w[a][b] = max(w[a+x[j]][b+y[j]]+1, w[a][b]);
            }
        }
    }
    if(k == 0) w[a][b] = 1;
}
int main(){
    cin >> n;
    for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) cin >> q[i][j];
    for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) bfs(i, j);
    for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) m = max(w[i][j], m);
    cout << m;
}