[Algorithm] Baekjoon 1520번 : 내리막 길

https://www.acmicpc.net/problem/1520

1520번: 내리막 길

int n, m;
 
int dir[4][2] = { {-1,0}, {1,0}, {0,-1}, {0,1} };
int arr[501][501];
int answerCount = 0;
 
 
void DFS(int curY, int curX)
{
    if (curY == n - 1 && curX == m - 1)
    {
        ++answerCount;
        return;
    }
 
    for (int i = 0; i < 4; ++i)
    {
        int nextY = curY + dir[i][0];
        int nextX = curX + dir[i][1];
 
        if (nextY < 0 || nextY >= n) continue;
        if (nextX < 0 || nextX >= m) continue;
        if (arr[nextY][nextX] >= arr[curY][curX]) continue;
 
        DFS(nextY, nextX);
    }
}
 
 
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
 
    cin >> n >> m;
 
    for (int i = 0; i < n; ++i)
    {
        for (int j = 0; j < m; ++j)
        {
            cin >> arr[i][j];
        }
    }
 
    DFS(0, 0);
 
    cout << answerCount;
}
 
 

위는 완전탐색 코드이다. 당연히 시간초과...에 걸린다.

DP카테고리 문제만 푸는 중이라 DP풀이를 해야하는건 알고있는데, 혹시나해서 완전탐색 해봤다.

물론 시간초과에 걸렸고, 다시 dp를 적용해서 풀이를 해보려했다.

 

 

 

 
int n, m;
int dir[4][2] = { {-1,0}, {1,0}, {0,-1}, {0,1} };
int arr[501][501];
int dp[501][501];
 
 
int DFS(int curY, int curX)
{
    if (curY == n - 1 && curX == m - 1)
    {
        return 1;
    }
    if (dp[curY][curX] != 0x3f3f3f3f) return dp[curY][curX];
    
    dp[curY][curX] = 0;
 
    for (int i = 0; i < 4; ++i)
    {
        int nextY = curY + dir[i][0];
        int nextX = curX + dir[i][1];
 
        if (nextY < 0 || nextY >= n) continue;
        if (nextX < 0 || nextX >= m) continue;
        if (arr[nextY][nextX] >= arr[curY][curX]) continue;
 
        dp[curY][curX] += DFS(nextY, nextX);
    }
 
    return dp[curY][curX];
}
 
 
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
 
    cin >> n >> m;
    
    for (int i = 0; i < n; ++i)
    {
        for (int j = 0; j < m; ++j)
        {
            cin >> arr[i][j];
        }
    }
 
    memset(dp, 0x3f, sizeof(dp));
    DFS(0, 0);
 
    cout << dp[0][0];
}

 

 

아예 dp로만 푸는건가 싶어서 고민해봤지만, 이동방향이 자유자재라서 아마 DFS개념도 들어가지않을까? 하고 풀이를 봤는데 생각이 맞긴 맞았다.

DP[I][K]를 [I][K]지점에서 목표지점까지 가기위한 경우의 수..라고 가정하고 생각하고 DFS를 돌려본다고 생각해보자.

DFS는 먼저 깊게 파고들기 때문에 결국 '목표지점 주위'에서부터  '각 지점에서 목표지점까지 가는 경우의 수'들이 차곡차곡 업데이트가 된다.

그렇기 때문에 DP값 업데이트가 가능하고, 그것을 토대로 불필요한 탐색에 대해선 바로 되돌려버리는 것이 가능하다.

불필요한걸 되돌려야 시간초과에 안걸리기 때문에 반드시 이 부분을 생각해야한다.

 

처음 값을 0x3f3f3f3f로 초기화 시켜놨었기 때문에, dfs탐색도중에 dp[i][j] = 0x3f3f3f3f값을 만나게 되면 아직 해당지점에서 목표지점까지 탐색이 번지지않았기 때문에 그대로 탐색을 수행해준다

다만, 처음 초기화값인 0x3f3f3f3f가 '아니라면', 이전에 탐색을 진행했었던것이기 때문에 더이상 탐색을 하지않고 바로 해당값을 return시키면 된다.