백준 1937번. 욕심쟁이 판다(c++) / DFS+DP

재귀와 dp를 함께 사용하는 아주 전형적인 문제 중 하나이다!

어느정도 난이도도 있으면서 감을 잡기 좋은? 문제인 것 같다.

 

[메인 로직]

dp배열을 -1의 값으로 초기화해놓고 판다가 출발하는 좌표보다 더 많은 대나무를 가지고 있는 영역의 dp값을 가져와서 +1씩 더하는 논리로 구현했다.

가지치기를 할 수 있는 부분이 바로 dp값이 -1이 아닌 경우는 이미 이전에 방문을 해서 그 영역에서 최대 몇 일을 버틸 수 있는지 메모이제이션을 해놓은 것이기 때문에 연산을 하지 않고 return dp[x][y]을 하고 바로 넘어갈 수 있다. (-> 매우 시간 절약!)

 

#include <iostream>
#include <queue>
 
using namespace std;
 
int n;
int map[501][501] = {0, };
int dp[501][501] = {0, };
int dx[4] = {-1, 1, 0, 0};
int dy[4] = {0, 0, -1, 1};
int ans = 0;
 
void pandaSearch()
{
    for(int i=0; i<n; i++){
        for(int j=0; j<n; j++){
            queue<pair<int, int>> q;
            q.push(make_pair(i, j));
            int visited[501][501] = {0, };
 
            while(!q.empty())
            {
                int x = q.front().first;
                int y = q.front().second;
                visited[x][y] = 1;
                q.pop();
 
                for(int k=0; k<4; k++){
                    int nx = x+dx[k];
                    int ny = y+dy[k];
                    if(0<=nx && nx<n && 0<=ny && ny<n && !visited[nx][ny]){
                        if(map[nx][ny]<=map[x][y]) continue;
                        if(dp[nx][ny]<dp[x][y]+1){
                            visited[nx][ny] = 1;
                            dp[nx][ny] = dp[x][y]+1;
                            q.push(make_pair(nx, ny));
                        }
                    }
                }
            }
        } 
    }
}
 
int main()
{
    cin>>n;
    for(int i=0; i<n; i++){
        for(int j=0; j<n; j++){
            cin>>map[i][j];
        }
    }
 
    pandaSearch();
 
    for(int i=0; i<n; i++){
        for(int j=0; j<n; j++){
            ans = max(ans, dp[i][j]);
        }
    }
 
    cout<<ans+1<<"\n";
 
    return 0;
}