[BOJ] C++ 1520: 내리막 길 - DFS인데 이제 DP를 곁들인...

1520번: 내리막 길

---

조건제한이 걸린 경로를 찾는 문제이다. 가장 먼저 떠올린 풀이는 dp [i][j]를 (i, j)까지 도달할 수 있는 경우의 수로 두고 네 방향 모두에서 (i, j)로 도달할 수 있으므로 4방향을 순차적으로 채우는 방법이었다. 이 방법은 아래와 같은 케이스를 잡아내지 못했다.

다음에 떠올린 방법은 DFS였다. DFS에서 백트래킹 느낌으로 메모이제이션을 떠올릴 수 있었다. 어떤 점 (i, j)에서 더 이상 갈 수 있는 곳이 없으면 (i, j)에 도달하면 바로 종료하는 방식으로 쓸 수 있고, (i, j)에서 특정 방향으로 진행했을 때 그 점에서 목적지까지의 경우의 수를 알고 있다면 이것도 써먹을 수 있다. 그럼 구현 사항을 정리해 보자.

1. DFS 방식으로 다음 진행 방향 정하기 (nx, ny)
2. (nx, ny)에서 목적지까지 도달할 수 있는 경우의 수를 구했다면 그 값 쓰기 (DP)

여기서 특이사항은 아직 방문하지 않은 점의 dp값을 0으로 둔다면 해당 점에서 목적지까지 도달할 수 없는 경우도 dp의 값이 0이므로 중복된다. 따라서 초기 dp값을 -1로 세팅하고 방문할 곳이 없다면 0으로 설정하는 방식으로 구현했다.

 

그럼 어떤 점에 도달하면 어떻게 알고리즘이 작동할지 생각해 보자.

네모 점에서 동그라미 점으로 진행했다고 생각하자. 네모 점은 동그라미에서 목적지까지 도달하는 경우의 수를 구해야 한다. 그리고 동그라미 점에서는 1번, 2번, 3번 방향에 대한 점의 dp값이 그림처럼 구해져 있다고 하자. 그럼 모두 더해주면 동그라미 점의 dp값이 정해지고 네모 점을 계산할 수 있다. 결괏값을 누적시키는 DFS 느낌으로 구현하면 된다.

 

구현이 은근히 헷갈리는데 DFS를 많이 해보는 방법밖에 없다.

/** DP 1520 내리막 길 **/
#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
using namespace std;

int n, m;
int board[700][700], dp[700][700];
int dx[4] = {0, 1, -1, 0};
int dy[4] = {1, 0, 0, -1};

int func(int x, int y)
{
    // base condition 1 : 현재 방문한 곳이 이미 dp값을 구한 곳이면 그 값 쓰면 됨.
    // 방문 배열을 따로 쓰지 않고 방문하지 않은 곳은 -1로 갈 수 없는 곳은 0으로 기록
    if (dp[x][y] != -1)
        return dp[x][y];
    // base condition 2 : 목적지 도달
    if (x == n - 1 && y == m - 1)
        return 1;

    // (x, y)에서 아무곳도 갈 수 없으면 그것도 알려줘야 함.
    dp[x][y] = 0;

    for (int dir = 0; dir < 4; dir++)
    {
        int nx = x + dx[dir], ny = y + dy[dir];
        if (nx < 0 || ny < 0 || nx >= n || ny >= m)
            continue;
        if (board[x][y] > board[nx][ny])
            dp[x][y] += func(nx, ny);
    }
    // for문 다 돌았으면 x, y에서 가능한 방문이 다 끝났다는 뜻이다.
    // 그럼 x, y를 호출한 함수에서 현재 x, y가 nx, ny가 된다.
    // 거기서의 nx, ny에서 목적지까지 경우의 수를 리턴해주면 된다.
    return dp[x][y];
}

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    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 << func(0, 0);
}