[1520] 내리막 길 - C++

---

문제

DFS를 사용하여 이미 지나간 흔적이 있는 경로는 계산하지 않는 방법으로 구현해야 한다. 

그렇기에 DP도 사용하여 흔적을 만들어야 함을 알 수 있다.

 

DP[i][j] = [i, j] 지점에서 부터 도착지점까지 갈 수 있는 경우의 수

 

입력을 받을 때 DP를 -1로 초기화해준다, -1은 아직 방문하지 않았다는 뜻이다.

 

이 문제를 풀며 놀랐던 부분이 있다면, DFS를 사용하는데 Stack을 사용하지 않고 바로바로 호출하는 것이었다.

int dfs(int x, int y){
  if(dp[x][y] != -1)return dp[x][y];
  if(x == n-1 && y == m-1) return 1;
  dp[x][y] = 0;
  for(int dir = 0; dir < 4; ++dir){
    int nx = x + dx[dir];
    int ny = y + dy[dir];
    if(nx < 0 || nx >= n || ny < 0 || ny >= m)continue;
    if(board[x][y] > board[nx][ny]) dp[x][y] += dfs(nx, ny);
  }
  return dp[x][y];
}

현재 나의 위치를 0으로 바꾼 후

네 방향을 모두 둘러보며 나보다 작은 곳으로 바로 이동하며 반복한다.

이미 방문하여 도착지점까지 가는 총경우의 수를 알게 된다면 값을 리턴한다.

 

이렇게 값을 끌어 올 수 있구나 하며 정말 감탄했다.

---

코드

#include <bits/stdc++.h>

using namespace std;
void init(){
  ios_base::sync_with_stdio(false);
  cin.tie(0);
  cout.tie(0);
}

int n, m;
int board[501][501];
int dp[501][501];

int dx[4] = {0,0,-1,1};
int dy[4] = {1,-1,0,0};

int dfs(int x, int y){
  if(dp[x][y] != -1)return dp[x][y];
  if(x == n-1 && y == m-1) return 1;
  dp[x][y] = 0;
  for(int dir = 0; dir < 4; ++dir){
    int nx = x + dx[dir];
    int ny = y + dy[dir];
    if(nx < 0 || nx >= n || ny < 0 || ny >= m)continue;
    if(board[x][y] > board[nx][ny]) dp[x][y] += dfs(nx, ny);
  }
  return dp[x][y];
}

int main(){
  init();
  cin >> n >> m;
  for(int i= 0; i < n; ++i){
    for(int j = 0; j < m; ++j){
      cin >> board[i][j];
      dp[i][j] = -1;
    }
  }
  cout << dfs(0, 0) << '\n';
  return 0;
}

---

글을 마치며

어려운 문제였다.

문제에 대해 고민하며, 경로를 중복하여 가지 않도록 위 풀이와 같이 DP를 사용해야겠다 생각해 냈지만 막상 구현하려니 쉽지 않았다.

그래서 그런가 정답 풀이를 보고 정말 감탄했다.

이 아이디어는 계속 기억하고 싶어 글로 남겨 본다.