[백준] 1520번 : 내리막 길 (C++)

1520번 : 내리막 길

---

문제)

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

 

 

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

 

 

 

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

 

 

 

 

입력 :

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

 

 

 

출력 :

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

 

 

 

 

 

 

풀이)

 

// 1520. 내리막 길
#include <iostream>
#include <vector>
 
using namespace std;
 
int n, m;
vector<vector<int>> vec;
vector<vector<int>> visited;
 
int dx[] = { -1, 0, 1, 0 };
int dy[] = { 0, -1, 0, 1 };
 
int dp[510][510];
 
int recur(int x, int y)
{
    if (x == n - 1 && y == m - 1) return 1;
 
    if (dp[x][y] != -1) return dp[x][y];
 
    int ret = 0;
 
    for (int i = 0; i < 4; i++)
    {
        int nx = x + dx[i];
        int ny = y + dy[i];
    
        // 지도를 벗어나는 경우
        if (nx < 0 || nx >= n) continue;
        if (ny < 0 || ny >= m) continue;
        
        // 이미 방문한 곳인 경우 (굳이 안해도 되긴 함)
        if (visited[nx][ny] == 1) continue;
        
        // 내리막길 조건
        if (vec[x][y] <= vec[nx][ny]) continue;
 
        visited[nx][ny] = 1;
        ret += recur(nx, ny);
        visited[nx][ny] = 0;
    }
 
    dp[x][y] = ret;
 
    return ret;
}
 
 
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
 
    cin >> n >> m;
    vec.resize(n, vector<int>(m));
    visited.resize(n, vector<int>(m, 0));
    for (auto& ele : vec) for (int& e : ele) cin >> e;
 
    fill(&dp[0][0], &dp[509][510], -1);
 
    cout << recur(0, 0);
 
    return 0;
}
 
 

---

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

1520번: 내리막 길