BOJ 1937 욕심쟁이 판다

문제설명

문제에서 제시된 상황은 생각보다 간단하다.
n*n 크기의 배열로 정수값이 주어지고 상하좌우로 연결하는데 현재보다 더 큰 정수 값을 찾아가도록 DFS 탐색을 해주면 된다.

걸림돌이 될 수 있는 부분은 모든 위치에서 대해서 4방향으로 계속해서 DFS 탐색을 해줘야 하기 떄문에 문제에서 제시한 사이즈 500 * 500이 query 숫자고 각각의 DFS 탐색이 드는 비용에 따라서 시간 초과 문제가 발생하거나 혹은 스택 오버플로우 문제가 발생할 수 있겠다는 지점인데 사실 배열의 크기 자체가 작아서 문제가 생길지는 정확히 모르겠다.

일단 효율적인 프로그램의 개념에서라도 memoization 기법을 이용해서 반복적인 DFS 탐색을 피해주는 것이 좋을 것으로 보인다. 각 지점에서 자신보다 큰 정수를 찾아서 DFS 탐색을 해나가게 되는데 이미 특정 지점에서 가볼 수 있는 깊이를 탐색해놓았다면 다른 루트를 통해서 특정 지점에 도달했을 경우 탐색해놓은 값을 그대로 이용해주는 방식으로 활용하는 것이다.

memoization 활용을 위해서 DP[i][j]의 값은 (i,j)의 위치에서 탐색할 수 있는 가장 깊은 깊이로 설정하고 DFS 탐색시 탐색에 들어오게 되면 기본적으로 자신의 위치 자체를 봤기 때문에 깊이 값을 1로 잡고 상하좌우 더 갈 수 있는 위치에서 탐색해놓은 값을 더해놓는다. 최종적으로 4방향의 탐색 중에서 가장 깊은 깊이를 잡아서 현재 DP 값에 저장해놓는 재귀적 방식으로 함수를 설정한다.

#include <bits/stdc++.h>

using namespace std;
using ll = long long;
using pii = pair <ll, ll>;

vector<vector<int>> arr;
vector<vector<int>> dp;

void dfs(int row, int col){
  
  // DFS 탐색 시 기본적으로 자기자신을 탐색했으므로 기본 깊이 1 설정
  int depth = 1;

  // 상하좌우 4방향 탐색하면서 재귀함후 호출로 각 위치 DP값 업데이트 시키고
  // 이를 바탕으로 memoization 해줌(이미 깊이 탐색을 한 지점이면 이후 방문 시 DP값을 바로 활용)
  // 4방향 중 가장 깊은 곳을 선택해서 현재 DP의 값에 업데이트 해놓기
  // 상 탐색 가능
  if(arr[row][col] < arr[row-1][col]){
    if(dp[row-1][col]==0)
      dfs(row-1, col);
    depth = max(depth, 1+dp[row-1][col]);
  }
  // 하 탐색 가능
  if(arr[row][col] < arr[row+1][col]){
    if(dp[row+1][col]==0)
      dfs(row+1, col);
    depth = max(depth, 1+dp[row+1][col]);
  }
  // 좌 탐색 가능
  if(arr[row][col] < arr[row][col-1]){
    if(dp[row][col-1]==0)
      dfs(row, col-1);
    depth = max(depth, 1+dp[row][col-1]);
  }
  // 우 탐색 가능
  if(arr[row][col] < arr[row][col+1]){
    if(dp[row][col+1]==0)
      dfs(row, col+1);
    depth = max(depth, 1+dp[row][col+1]);
  }
  dp[row][col] = depth;
}

int main() {
  ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);

  freopen("inp.txt", "r", stdin);
  
  int N;
  cin >> N;
  arr.resize(N+2, vector<int>(N+2, -1));
  dp.resize(N+2, vector<int>(N+2, 0));
  
  // 대나무 크기 사이즈 입력받기
  for(int i=1; i<=N; i++){
    for(int j=1; j<=N; j++)
      cin >> arr[i][j];
  }

  // 각각의 지점들에서 DFS방식으로 큰 정수값을 찾아가면서 DP값 업데이트
  for(int i=1; i<=N; i++){
    for(int j=1; j<=N; j++){
      dfs(i, j);
    }
  }

  // 다시 DP배열 전체 읽어보면서 가장 깊은 탐색 깊이 답으로 설정해서 출력하기
  int ans = -1;
  for(int i=1; i<=N; i++){
    for(int j=1; j<=N; j++){
      cout << dp[i][j] << ' ';
      ans = max(ans, dp[i][j]);
    }
    cout << '\n';
  }
  cout << ans;
}

예제입력1에 따른 DP 배열 값으로 각각의 지점에서 탐색할 수 있는 깊이를 나타내고 있다.