[백준/알고리즘] 1520번 내리막 길

엄청난 시간초과 재시도 후에 겨우 성공..

우선 문제를 어떻게 풀었는지 설명하고 나서 시간초과가 난 원인까지 분석을 해보겠다.

처음에는 이문제를 그냥 DFS로 풀어봤는데 시간 초과가 났다 그냥 DFS로 풀게되면 너무나 많은 경로를 탐색하기 때문에 당연히 시간초과가 날수밖에 없다. 상하좌우 4방향으로 이동이 가능하고 칸수가 최대 500x500 = 250000개이므로 4의 250000승이라는 어마어마한 경로의 경우의수가 존재하기 때문에 그냥 DFS로는 절대 풀수 없는 문제이다.

그래서 DP로 풀어야 하는데, DP로 풀때도 주의사항이 있다. 

우선 코드를 먼저 보면 

int dfs(int x, int y)
{
    if (dp[x][y] != -1) return dp[x][y]; //값이 이미 있는경우 또계산하지말고 있는값 리턴
    if (x < 0 || x >= n || y < 0 || y >= m) return 0; //범위 벗어난 경우는 불가능하므로 0리턴
    if (x == 0 && y == 0) return 1; //기저사례
 
    dp[x][y] = 0;
    for (int i = 0; i < 4; i++)
    {
        int nextX = x + a[i];
        int nextY = y + b[i]; //상하좌우 모두 이동가능하므로.
        
        if (input[nextX][nextY]>input[x][y])
            dp[x][y] += dfs(nextX, nextY);
    }
 
    return dp[x][y];
}

우선 나같은 경우에는 n-1,m-1부터 0,0까지 차례로 내려가는 경우로 dfs를 구현했다.

4 5
50 45 37 32 30
35 50 40 20 25
30 30 25 17 28
27 24 22 15 10

예제에서 17에서 50까지 갈수있는 경로의 수는 17보다 큰 수인 25 20 28에 적혀있는 경로의 수의 합이다.

좀더 쉽게 설명하면 

25에서 50까지의 경로의 수 == 17에서 50까지의 경로의 수 이고,

20에서 50까지의 경로의 수 == 17에서 50까지의 경로의 수 이고,

28에서 50까지의 경로의 수 == 17에서 50까지의 경로의 수 이다. 

따라서 세가지 경로의수를 합쳐야 17에서 50까지의 경로의 경우의수인것이다.

즉 17~50까지의 경로라는 문제를

25~50, 20~50, 28~50의 경로의수인 작은 부분문제의 합으로 나눈 DP문제라고 볼 수 있는 것이다.

이제 시간초과가 난 이유를 설명해보겠다.

우선 처음에는 그냥 무식하게 DFS를 돌려서 시간초과가 났었고, 그 후에 DP로 수정했는데도 시간초과가 나서 

도저히 찾을 수가없어서 구글의 힘을 빌렸다.

그래서 원인을 찾아냈는데 방법 자체는 맞았지만 약간 수정해야 하는 부분이 있었다.

처음에 DP 2차원 배열을 0으로 초기화 했고, DP[I][J] 에 들어있는 값이 0이 아닌경우 그 칸에서 0,0까지의 경로의 수는 이미 계산됬다고 보고 중복 계산을 피하기 위해서 재귀함수를 리턴시켰다.

근데 여기서 문제가 있는데 DP를 0으로 초기화 해버리면 재귀 호출 과정에서 현재 점 보다 상하좌우 좌표가 더 작기 때문에 현재 경로의수가 0인지 아니면 계산을 아직 안해서 0인지를 구분할수없게 돼버린다.

즉 계산을 해서 0인지, 계산을 안해서 0인지 구분이 안가기 때문에 같은 경로를 매우 많은 횟수로 반복을 하기 때문에 시간초과가 났다.

이해가 안가시는분은  

      1

2    5    3     이렇게 되있는 부분을 생각해보면 이해가 될것이다.

      4

재귀함수 호출 조건에서 현재점보다 주변의 점들이 더 커야 한다는 조건이 있는데 위와 같은 상황에선 재귀 함수 호출 조건을 만족하는 점이 하나도 없으므로 현재(5가표시된)점의 dp[i][j]에는 0이 들어가게 될것이다. 

근데 이 0이라는 값이 계산이 되서 0인지 아니면 계산이 안되서 0인지 구분할수 없기 때문에 알고리즘을 돌리면 계속 저 부분은 계산이 안된거라고 판단을 하기떄문에 반복되게 된다.

그래서 DP를 처음에 MEMSET을 이용해 -1로 초기화 한다음에 제출해보니 성공했다.

앞으로도 웬만하면 DP를 -1로 초기화 하는게 정신건강에 좋을것 같다.

전체코드

#define _CRT_SECURE_NO_WARNINGS
#include<iostream>
#include<algorithm>
#include<memory.h>
using namespace std;
int n,m;
int input[501][501];
int dp[501][501]; //값 저장 메모장
int a[4] = { 1, 0, -1, 0 };
int b[4] = { 0, 1, 0, -1 };
int dfs(int x, int y)
{
    if (dp[x][y] != -1) return dp[x][y]; //값이 이미 있는경우 또계산하지말고 있는값 리턴
    if (x < 0 || x >= n || y < 0 || y >= m) return 0; //범위 벗어난 경우는 불가능하므로 0리턴
    if (x == 0 && y == 0) return 1; //기저사례
 
    dp[x][y] = 0;
    for (int i = 0; i < 4; i++)
    {
        int nextX = x + a[i];
        int nextY = y + b[i]; //상하좌우 모두 이동가능하므로.
        
        if (input[nextX][nextY]>input[x][y])
            dp[x][y] += dfs(nextX, nextY);
    }
 
    return dp[x][y];
}
 
int main()
{
    cin >> n >> m;
 
    for (int i = 0; i < n; i++)
        for (int j = 0; j < m; j++)
            scanf("%d", &input[i][j]);
 
    memset(dp, -1, sizeof(dp));
 
    printf("%d", dfs(n-1, m-1));
 
    return 0;
}