[알고리즘 문제] 백준1520 - 내리막 길

www.acmicpc.net/problem/1520

1520번: 내리막 길

처음에 dfs를 생각했다. 근데 출력결과를 보면 최대10억까지 나올 수 있다고 되어있다. 그렇다면 탐색해야 하는 경우의 수는 10억보다 더 많을 것이고...무조건 시간초과가 나온다. 또 각 위치에서 4방향을 움직일 수 있고 가로/세로의 크기가 최대 500이기 때문에 시간 복잡도는 4^250000이 된다. 아무튼 일반적인 dfs로 풀면 안된다.

 

다음 생각해본 방법은 dp로 푸는 방법이다. 현재 dp[y][x]에서 4방향으로 움직일 수 있으면 해당 위치에서 dp[y][x]+1값을 저장하는 방식인데, 이 방법도 문제가 있다. 이 경우는 미래에 존재할 수 있는 경우의 수를 예측하지 못하는 문제가 있고 dp[y][x]의 값을 신뢰할 수가 없다.

 

다른 분의 풀이를 참고하였꼬 이 문제는 dp + dfs 방법을 혼합해야 한다. dfs를 하면서 그 결과값을 dp[][]에 저장하는 방식으로 해결할 수 있다. 그리고 dp배열을 -1로 초기화 하고, -1이 부분은 아직 탐색하지 않은 부분으로 정의한다.

#include <iostream>

using namespace std;

int height, width;
int arr[501][501] = {};
int dp[501][501] = {};

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

int dfs(int y, int x)
{
    if (y == height - 1 && x == width - 1)
    {
        return 1;
    }
    if (dp[y][x] != -1)
    {
        return dp[y][x];
    }
    dp[y][x] = 0;
    for (int i = 0; i < 4; i++)
    {
        int newX = x + dx[i];
        int newY = y + dy[i];

        if (arr[newY][newX] < arr[y][x] && newX >= 0 && newY >= 0 && newX < width && newY < height)
        {
            dp[y][x] += dfs(newY, newX);
        }
    }
    return dp[y][x];
}
int main()
{
    cin >> height >> width;

    for (int y = 0; y < height; y++)
    {
        for (int x = 0; x < width; x++)
        {
            cin >> arr[y][x];
            dp[y][x] = -1;
        }
    }

    cout << dfs(0, 0) << endl;
    return 0;
}