백준 1520번 [내리막 길](C++) -yes6686- 티스토리

백준 문제 풀이: 1520 [내리막 길]

---

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

문제 설명:

지도의 각 칸에는 높이가 주어지며, (0,0)에서 시작하여 (n-1,m-1)까지 가는 경로 중에서 항상 내리막길만 이동하는 경우의 수를 구하는 문제입니다.

즉, 현재 위치보다 낮은 위치로만 이동할 수 있으며, 가능한 모든 경로의 개수를 출력해야 합니다.

---

문제 해결 코드

#include <iostream>
using namespace std;

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

int arr[501][501]; // 지도 정보
long long dp[501][501]; // 메모이제이션 배열
int n, m;

// 깊이 우선 탐색 (DFS) + 동적 프로그래밍 (메모이제이션)
int dfs(int x, int y) {
    if (x == n - 1 && y == m - 1) return 1; // 목적지 도달 시 1 반환
    if (dp[x][y] != -1) return dp[x][y]; // 이미 계산된 경우 반환

    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 && arr[x][y] > arr[nx][ny]) {
            dp[x][y] += dfs(nx, ny);
        }
    }

    return dp[x][y];
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);

    cin >> n >> m;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            cin >> arr[i][j];
            dp[i][j] = -1; // DP 배열 초기화 (방문하지 않은 상태)
        }
    }

    cout << dfs(0, 0) << '\n'; // 시작점에서 DFS 탐색 후 결과 출력

    return 0;
}

예제 입력:

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

예제 출력:

3

---

코드 설명

• 핵심 알고리즘: DFS + DP(메모이제이션)을 사용하여 중복 계산을 줄이고 최적의 경로 개수를 계산합니다.
• 구현 세부사항:
  • DFS로 탐색하며, 현재 위치보다 낮은 위치로만 이동할 수 있도록 조건을 설정합니다.
  • DP 배열을 활용하여 이미 방문한 경로를 저장하고, 중복 연산을 방지합니다.
  • 목적지에 도착한 경우 1을 반환하고, 이후 경로마다 가능한 경우의 수를 누적합니다.
• 시간 복잡도: O(N × M) (메모이제이션을 사용하여 각 위치를 한 번만 탐색)

---

결과

주어진 지도를 따라 내리막길만 이동하여 목적지까지 도달하는 경로의 개수를 정확히 계산합니다. DFS와 DP를 활용한 최적화 기법을 연습하기 좋은 문제입니다. 추가적인 질문이나 개선 사항이 있다면 댓글로 알려주세요!