# 1520. 내리막 길

관련 알고리즘 : DP, DFS

 

문제 링크 : https://www.acmicpc.net/problem/1520

1520번: 내리막 길

 

---

풀이 과정

무작정 상하좌우 네 방향을 모두 탐색하는 방법으로 한다면, 시간초과가 발생할 것이다.

따라서 dp를 이용한 메모이제이션을 통해 시간과 더불어 중복을 감소시켜 주어야 한다. 

 

재귀를 사용하여 현재 좌표(x,y)에서 상, 하, 좌, 우 중 어느 곳으로 이동할 수 있는지 확인하고, 마지막 목적지인 (m,n)에 도착할 수 있는 경로를 찾을 때마다 dp[x][y]+=1 해주면 된다.

이 때, dp[x][y]는 (x,y)에서 (m,n) 까지 갈 수 있는 경로의 가짓수를 의미한다.

 

즉, 

1. 상하좌우 탐색을 통해 조건(낮은 높이로만 갈 수 있음)을 만족하는지 확인
2. 만족할 시 상/하/좌/우로 이동한 위치가 지도 좌표 내 범위에 있는지 확인
3. 2를 만족 시, 높이가 현재 위치의 높이보다 낮은지 조건 확인
4. 3까지 만족 시, 재귀를 통해 현재 위치에서 목적지까지 갈 수 있는 경로 수 확인 후, (m,n)에 도착하면 dp[x][y]에 1 증가됨

가 코드의 흐름이 된다.

 

---

 

해결 코드 - C++

 

// 백준 1520 - 내리막길

#include <iostream>
#include <cstring>
#define max 500

using namespace std;


int n, m;
int coo[max][max]; // 해당 좌표값의 높이 저장
int dp[max][max]; // 경로 가짓수 저장

int dx[] = { 0, 0, -1, 1}; // 상하좌우
int dy[] = { 1, -1, 0, 0}; 

void input()
{
    cin >> n >> m;
    for (int i=0; i<n; i++)
    {
        for (int j=0; j<m; j++)
        {
            cin >> coo[i][j];
            dp[i][j] = -1; // 0으로 초기화하면 경우의 수가 0일 때와 겹치므로 -1로 초기화
        }
    }
}
 
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[x][y] = 0;
    for (int i=0; i<4; i++) // 상하좌우 경로탐색
    {
        int move_x = x + dx[i]; // 이동 후 x위치 move_x
        int move_y = y + dy[i]; // 이동 후 y위치 move_y
        if (move_x>=0 && move_x<n && move_y>=0 && move_y<m) // 좌표 범위 내 있는지 확인
        {
            if (coo[move_x][move_y] < coo[x][y]) // 높이가 현재 높이보다 낮다면
            {
                dp[x][y] = dp[x][y] + dfs(move_x, move_y); // 재귀 이용하여 dp배열에 저장
            }
        }
    }
    return dp[x][y];
}

int main()
{
    input();
    int ans = dfs(0,0);
    cout << ans << endl;
}

 

문제 풀 때 좌표값 배열 범위를 헷갈려서 계속 틀렸습니다 가 나왔는데, 처음에 발견 못하고 고치느라 애먹었다.

애초에 헷갈리지 않도록 max값을 501로 설정하고 1부터 500까지의 인덱스를 이용하는 것이 좋을 듯 하다.