백준 1937번 욕심쟁이 판다[C++]

1. 문제 풀이

문제 유형은 깊이 우선 탐색을 사용하는 동적 계획 알고리즘이었습니다. 문제의 요구 조건을 시간복잡도의 개념을 빼놓고 고민해 보면 단순합니다. 2차원 배열에 각 정점을 깊이 우선 탐색하면서 최장 거리를 찾는 문제입니다. 하지만 이 경우 임의의 칸을 중복 방문한다는 문제점이 발생하고 이로 인해 시간초과가 납니다. 따라서 적절하게 메모이제이션을 통해 최적화를 해야합니다.

 

d[i][j] = k : (i, j)에서 출발했을 때 k번 까지 이동하며 대나무를 먹는다.

 

d[i][j]가 아직 방문하지 않은 곳이면 0으로 초기화를 해놓고 깊이 우선 탐색을 진행해 임의의 값 k로 갱신되었다고 해봅시다. 이렇게 갱신된 테이블은 중복 방문을 방지하는 문턱 역할을 합니다. 만약에 다른 위치에서 탐색을 하던 도중 이미 방문해 갱신된 테이블에 도착을 했다고 가정해 봅시다. 이미 갱신된 이 테이블은 굳이 더 방문해보지 않아도 k번이라는 사실을 알 수 있습니다.

 

2. 코드

#include <bits/stdc++.h>
using namespace std;
typedef long long ll; typedef unsigned long long ull; typedef pair<int,int> pi; typedef pair<ll, ll> pl;
typedef tuple<int, int, int> ti; typedef tuple<ll, ll, ll> tl; typedef vector<int> vi; typedef vector<ll> vl;
typedef vector<pi> vpi; typedef vector<pl> vpl; typedef vector<ti> vti; typedef vector<tl> vtl;
typedef vector<string> vs; typedef vector<bool> vb; typedef queue<int> qi; typedef queue<ll> ql;
typedef queue<pi> qpi; typedef queue<pl> qpl; typedef queue<ti> qti; typedef queue<tl> qtl;
#define fastio(x, y) cin.tie((x))->sync_with_stdio((y))
#define X first
#define Y second
#define pb push_back
#define sz(x) (int((x).size()))
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
const char nl = '\n';
const int dx[4] = { 1, 0, -1, 0 };
const int dy[4] = { 0, 1, 0, -1 };
int n;
int board[505][505];
int d[505][505];
int dfs(int cx, int cy){
  if(d[cx][cy] != 0) return d[cx][cy];
  bool flag{};
  for(int dir = 0; dir < 4; dir++){
    int nx = cx + dx[dir];
    int ny = cy + dy[dir];
    if(nx < 0 || nx >= n || ny < 0 || ny >= n || board[cx][cy] >= board[nx][ny]) continue;
    flag = 1;
    d[cx][cy] = max(d[cx][cy], dfs(nx, ny) + 1);
  }
  return (flag ? d[cx][cy] : 1);
}
int main() {
  fastio(nullptr, false);
  cin >> n;
  for(int i = 0; i < n; i++)
  for(int j = 0; j < n; j++)
    cin >> board[i][j];
  
  for(int i = 0; i < n; i++){
    for(int j = 0; j < n; j++){
      if(d[i][j]) continue;
      d[i][j] = dfs(i, j);
    }
  }
  cout << *max_element(&d[0][0], &d[n][n+1]);
}

 

3. 제출 결과