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

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

처음에 그냥 혹시나하고 기본 dfs로 했는데 시간 초과가 났다 ㅠ

그래서 이건 백퍼 dp 문제인데 분명 ㅠㅠ...

하면서 한시간 동안 고민했으나 그렇다 할 알고리즘이 떠오르지 않았다.. 역순으로 채우는 것 까지는 얼추 생각했으나 ㅠㅠ

나의 패인은 딱 하나의 알고리즘을 사용하려고 했던 것인 것 같다.

DFS 아니면 DP 둘 중에 하나를 선택해서 문제를 풀려고 했더니 도저히 문제를 풀 수가 없었당..

이 문제는 DFS와 DP를 모두 사용하여 푸는 문제이다!

DP 배열을 역순으로 채워나가면서 현재 좌표(_x, _y)에서 다음 좌표(mx, my)로 갈 때에 그 좌표가 이미 방문했던 공간이면 현재 좌표까지의 갈 수 있는 경우의 수는 dp(_x,_y) + dp(mx, my)가 된다.

이미 갔던 길의 경우의 수를 저장해두었다가 이용함으로써 프로그램 시간을 절약할 수 있다.

map[4][5]

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

주어진 정보가 위와 같을 때 dp는 아래의 순서로 채워진다.

dp[4][5]

0	0	0	0	0
0	0	0	0	0
0	0	0	0	0
0	0	0	1	0

0	0	0	0	0
0	0	0	0	0
0	0	0	1	0
0	0	0	1	0

0	0	0	0	0
0	0	0	1	0
0	0	0	1	0
0	0	0	1	0

0	0	0	0	0
0	0	0	1	1
0	0	0	1	0
0	0	0	1	0

0	0	0	0	1
0	0	0	1	1
0	0	0	1	0
0	0	0	1	0

0	0	0	1	1
0	0	0	1	1
0	0	0	1	0
0	0	0	1	0

0	0	0	2	1
0	0	0	1	1
0	0	0	1	0
0	0	0	1	0

0	0	2	2	1
0	0	0	1	1
0	0	0	1	0
0	0	0	1	0

#include<iostream>
using namespace std;
 
int M, N;
int map[501][501];
int dp[501][501];
bool visited[501][501];
 
int dx[4] = { 0,0,1,-1 };
int dy[4] = { 1,-1,0,0 };
 
int dfs(int _x, int _y)
{
    // 목적지에 도착하면 최초 경우의 수 1 반환
    if (_x == M - 1 && _y == N - 1)    return 1;
 
    // 이미 방문한 곳이면 그 곳의 값을 반환
    if (visited[_x][_y]) return dp[_x][_y];
 
    // 방문 여부 표시
    visited[_x][_y] = true;
 
    for (int i = 0; i < 4; i++)
    {
        int mx = _x + dx[i];
        int my = _y + dy[i];
 
        if (mx >= 0 && mx < M && my >= 0 && my < N)
        {
            if (map[_x][_y] > map[mx][my])
            {
                // 도착지점에서부터 출발지점까지 역순으로 경우의 수를 추가하면서 채워나간다.
                dp[_x][_y] += dfs(mx, my);
            }
        }
    }
    // 현재 좌표에서 갈 수 있는 곳이 없으면 현재 좌표까지 갈 수 있는 경우의 수를 반환
    return dp[_x][_y];
}
 
int main(void)
{
    cin >> M >> N;
 
    for (int i = 0; i < M; i++)
    {
        for (int j = 0; j < N; j++)
        {
            cin >> map[i][j];
        }
    }
 
    cout << dfs(0,0) << '\n';
 
    return 0;
}