[BOJ] 1520번 내리막 길

문제 바로가기

접근

DFS와 DP를 섞은 풀이이다. 먼저 배열 dp를 -1로 초기화해두고 탐색을 시작한다. 만일 dp[a][b]가 -1이라면 출발점으로부터 (a,b)까지의 경로를 탐색하라는 것이고, 아니라면 갈 수 있는 경로가 해당하는 수만큼 있다는 뜻이다.

출발점에서 시작해 도착점에 도달했을 때 1을 리턴하면, 마지막에 출발점에 저장된 dp의 값이 최종 경로의 수가 된다.

#include <bits/stdc++.h>
using namespace std;

#define MAX 502

int M, N;
int arr[MAX][MAX] = {0};
int dp[MAX][MAX] = {0};
int nx, ny;
int dy[4] = {-1, 1, 0, 0};
int dx[4] = {0, 0, -1, 1};

int dfs(int y, int x) {
  if(dp[y][x] != -1)
    return dp[y][x];
    
  if(y == M && x == N)
    return 1;
  dp[y][x] = 0;

  for(int k = 0; k < 4; k++) {
    ny = y + dy[k];
    nx = x + dx[k];
    if(arr[y][x] > arr[ny][nx])
      dp[y][x] += dfs(ny, nx);
  }
  return dp[y][x];
}

int main() {
  std::ios::sync_with_stdio(false);

  cin >> M >> N;
  for(int i = 1; i <= M; i++) {
    for(int j = 1; j <= N; j++) {
      cin >> arr[i][j];
      dp[i][j] = -1;
    }
  }

  cout << dfs(1, 1) << endl;
}