[C++] 백준 온라인 저지 1520번 내리막 길 풀이

목표지점에 가기 위해서 내리막 길로만 가는 경로의 갯수 구하는 문제

 

---

 

문제의 조건

 

이 지도는 아래 그림과 같이 직사각형 모양이며 여러 칸으로 나뉘어져 있다. 한 칸은 한 지점을 나타내는데 각 칸에는 그 지점의 높이가 쓰여 있으며, 각 지점 사이의 이동은 지도에서 상하좌우 이웃한 곳끼리만 가능하다.

현재 제일 왼쪽 위 칸이 나타내는 지점에 있는 세준이는 제일 오른쪽 아래 칸이 나타내는 지점으로 가려고 한다. 그런데 가능한 힘을 적게 들이고 싶어 항상 높이가 더 낮은 지점으로만 이동하여 목표 지점까지 가고자 한다. 위와 같은 지도에서는 다음과 같은 세 가지 경로가 가능하다.

 

 

 

지도가 주어질 때 이와 같이 제일 왼쪽 위 지점에서 출발하여 제일 오른쪽 아래 지점까지 항상 내리막길로만 이동하는 경로의 개수를 구하는 프로그램을 작성하시오.

 

입력

첫째 줄에는 지도의 세로의 크기 M과 가로의 크기 N이 빈칸을 사이에 두고 주어진다. 이어 다음 M개 줄에 걸쳐 한 줄에 N개씩 위에서부터 차례로 각 지점의 높이가 빈 칸을 사이에 두고 주어진다. M과 N은 각각 500이하의 자연수이고, 각 지점의 높이는 10000이하의 자연수이다.

 

출력

첫째 줄에 이동 가능한 경로의 수 H를 출력한다. 모든 입력에 대하여 H는 10억 이하의 음이 아닌 정수이다.

 

 

풀이 과정

 

 처음엔 스택을 사용해서 DFS로 풀어 봤는데 도착점에 도착 하고 나면 방문배열을 리셋하고 갈림길에서 다시 경로를 탐색하는 방식으로 했더니 시간 초과가 나서 통과하지 못 했습니다 ㅠ.ㅠ 그래서 구글링을 해 보니까 DFS + DP로 풀어야 한다고 하더라고요... DP로 메모이제이션을 하며 탐색 가짓수를 줄여주는 것이 핵심어었습니다... 그리고 DFS는 재귀로 구현할 것...(재귀를 별로 안 좋아해서 처음에는 스택으로 구현했었음)

 정리하자면,

- 탐색은 도착 지점에서부터 거꾸로 해 나간다. 

- DP 배열에 메모이제이션을 하며 이미 탐색을 했던 곳이라면 해당 인덱스 값을 출력한다. 

- 아직 탐색하지 않은 곳이면 여기에서부터 가능한 경로들을 탐색하며 가짓수를 알아온다. 

 

1. 지도 2차원 배열을 만들어 입력을 받고 해당 타일까지 올 수 있는 경로 수를 저장할 DP 2차원 배열을 만들면서 -1로 초기화 한다.(둘 다 크기는 똑같다) 

1-1. DP 배열에서 -1은 아직 탐색을 하지 않은 곳이라는 의미고

1-2. 도착 지점에서부터 거꾸로 탐색해 나가기 때문에 다음 타일이 현재보다 크고 아직 탐색을 하지 않았으면 여기까지 올 수 있는 경로의 갯수를 0으로 초기화하고 4방향 탐색을 시작한다. 

1-3. 만약 탐색하러 들어간 타일이 -1이 아니라면 이미 탐색을 한 곳이라는 의미다. 그러면 더 탐색을 할 필요없이 현재 타일의 경로 수를 반환한다. 

 

2. DFS를 재귀로 구현한다. DP 배열 인덱스에 경로 수를 저장할 수 있도록 구현한다. 

 

 

코드

 

#include <iostream>
#include <vector>

using namespace std;

int height, width; //높이, 너비 
vector<vector<int>> dir; //4방향 배열 
vector<vector<int>> board; //지도 배열
vector<vector<int>> DP; //DP 배열 
int dfs(pair<int, int> cur)
{
    if (-1 != DP[cur.first][cur.second]) return DP[cur.first][cur.second]; //이미 탐색했다면 현재 인덱스값 반환
    if (0 == cur.first && 0 == cur.second) return 1; //기저조건
    
    DP[cur.first][cur.second] = 0;
    for (int i = 0; 4 > i; i++)
    {
        auto next = make_pair(cur.first + dir[i][0], cur.second + dir[i][1]);
        if (0 > next.first || height <= next.first
            || 0 > next.second || width <= next.second)
            continue;
        if (board[next.first][next.second] > board[cur.first][cur.second])
            DP[cur.first][cur.second] += dfs(next);
    }
    
    return DP[cur.first][cur.second];
}

int main()
{
    dir.push_back({0,1});
    dir.push_back({0,-1});
    dir.push_back({1,0});
    dir.push_back({-1,0});
    
    cin >> height >> width;
    
    board.assign(height, vector<int>(width, 0));
    for (int i = 0; height > i; i++)
    {
        for (int j = 0; width > j; j++)
            cin >> board[i][j];
    }
    
    DP.assign(height, vector<int>(width, -1));
    
    int answer = dfs(make_pair(height - 1, width - 1));
    
    cout << answer;
    
    return 0;
}