백준 1520 내리막 길

오늘도 DP 문제이다. 2차원 지도를 입력으로 받아 0, 0 위치에서 N - 1, M - 1 위치까지 경로가 몇개 있는지 찾는 문제이다.

DP 없이 그냥 문제 푼다고 생각하면 DFS를 써서 탐색을 돌려버릴 것 같다. 하지만 맵 크기가 작은 편이 아니라 그렇게 돌리면 Timeout이 발생할 가능성이 크다.

 

처음에 DP 접근을 dp[i][j] = 0, 0에서부터 i, j 까지 경로의 수 라고 생각을 해봤는데 생각을 아무리 해봐도 잘 답이 나오지 않았다. 그러고 한번 뒤집어 접근을해봤다. dp[i][j] = i, j 에서부터 N-1, M-1 까지 경로의 수로 생각을 하고 접근을 했다. 이 방향이 더 좋았던 것 같다.

그리고, dp 배열을 채우는 과정은 DFS로 흘러가게 된다. 현재 픽셀에서, 다음 픽셀을 찾고(상하좌우) 다음 픽셀을 갈 수 있으면(맵 안쪽이고, 현재 위치보다 높이가 낮으면) dp 배열 현재 위치 값을 갱신한다. 갱신 은 dfs(다음 픽셀) 을 호출하여 더하는 과정이다.

마지막 위치일 경우 dfs 함수는 1을 리턴하고, 현재 위치 dp 배열이 이미 차있으면 그 값을 리턴한다.

 

그렇게 dp 를 갱신하고 dp[0][0] 을 출력하면 우리가 찾는 값이 나온다. 이거 짜면서 새삼 DFS에 스택을 쓴다는걸 느꼈다. 스택을 다른 자료형을 써서 작성하는게 아닌 함수 호출 스택을 쓴다는 느낌이 좀 특이했다. BFS를 한창 할때는 큐 하나 만들어서 썼었는데...

생각없이 BFS 코드는 이렇게 씁니다~ 가 아니라 원래 재귀를 쓰는 DFS 솔루션은 되게 Low 레벨에 대한 이해가 필요한 접근이구나... 라는 생각이 들었다.

---

#include <iostream>
#include <vector>
#include <string.h>
int map[501][501];
int dp[501][501];
int N, M;

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

int dfs(int x, int y)
{
    if (x == N - 1 && y == M - 1)
        return 1; // 마지막 위치일때.
    if (dp[x][y] != -1)
        return dp[x][y]; // dp 배열이 차 있는 경우는 그 값을 그냥 리턴해줌

    dp[x][y] = 0;
    for (int i = 0; i < 4; i++)
    {
        int nx = x + dx[i];
        int ny = y + dy[i];
        if(nx >= 0 && ny >= 0 && nx < N && ny < M)
        {
            if (map[nx][ny] < map[x][y])
                dp[x][y] = dp[x][y] + dfs(nx, ny);
        }
    }
    return dp[x][y];
}

int main()
{
    std::cin >> N >> M;

    for (int i = 0; i < N; ++i)
    {
        for (int j = 0; j < M; ++j)
            std::cin >> map[i][j];
    }
    memset(dp, -1, sizeof(dp));
    // 맵 크기와 같은 dp 배열? dp[i][j] -> 0,0 에서 i, j 자리까지 걸리는 거리 ㄴㄴㄴ.
    // 맵 크기와 같은 DP 배열 dp[i][j] -> i, j 에서 N-1, M-1까지 걸리는 거리

    std::cout << dfs(0, 0);
}

주말엔 조금 힘을 뺀것 같다. 주중에는 좀 힘을 주고 달려볼까 생각중이다. 이번주는 페이퍼워크 할게 많으니 글쓰기 대잔치가 벌어질 것 같다. 야호 하하하하...

 

오늘도 평온한 하루가 되길. 슨민.