백준 1520 - 내리막 길

문제 설명

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

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

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

---

 

 

 

 

 

 

제한 사항

---

 

 

 

 

 

 

풀이

문제를 요약하면, 현재 칸보다 높이가 낮은 칸으로만 이동하며 (1,1)부터 (N,M)까지 이동하는 경로의 개수를 구하는 것이다.

해당 문제는 DP와 DFS를 사용하면 쉽게 풀 수 있다.

DP에 기록할 값은 해당 칸에서 (N, M)까지 도착할 수 있는 경로의 개수이다.

예시를 봐보자.

(0, 0)에서 이동할 수 있는 칸은(1, 0), (0, 1)이다.

45와 35는 50보다 작기 때문이다.

이렇게 4방향을 탐색하며 갈 수 있는 칸에 DP값을 추가해주면 된다.

하지만, 하나의 칸을 순회하는 순서에 따라 결과가 달라진다.

(1, 3)인 20을 보면 위쪽, 왼쪽, 오른쪽 모두 접근 가능하다.

하지만, 25인 오른쪽 칸은 아직 갱신이 되지 않은 상태이다.

따라서, 이러한 순서를 보장하기 위해 반복문이 아닌 DFS를 통해 DP를 갱신하는 것이다.

DFS에서 현재 칸보다 작은 칸이 있다면 해당 칸에 방문하여 갱신된 DP의 값을 더해준다.

DFS를 진행하다 이미 방문한 칸이거나 (N, M)에 도착했다면 순회하지 않고 돌아간다.

DP에 기록되는 값은 다음과 같다.

• -1: 아직 방문하지 않은 칸
• 0: 방문할 경로가 존재하지 않는 칸
• 나머지: 경로의 개수

갱신된 DP의 값은 아래와 같다.

---

 

 

 

 

 

전체 코드

#include <stdio.h>
#include <cstring>
#include <string>
#include <vector>
#include <algorithm>
#include <iostream>
#include <sstream>
#include <cmath>
#include <climits>
#include <queue>
#include <map>
#include <unordered_map>
#include <set>

using namespace std;

int N, M;

vector<int> dy = { -1, 0, 1, 0 };
vector<int> dx = { 0, 1, 0, -1 };

vector<vector<int>> Board;
vector<vector<int>> dp;

int dfs(int y, int x)
{
    if (y == N && x == M) return 1;
    if (dp[y][x] != -1) return dp[y][x];

    dp[y][x] = 0;
    for (int i = 0; i < 4; i++)
    {
        int newY = y + dy[i];
        int newX = x + dx[i];

        if (newY <= 0 || newY > N || newX <= 0 || newX > M) continue;
        if (Board[newY][newX] < Board[y][x])
        {
            dp[y][x] += dfs(newY, newX);
        }
    }

    return dp[y][x];
}

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    cin >> N >> M;

    Board.assign(N + 1, vector<int>(M + 1));
    dp.assign(N + 1, vector<int>(M + 1, -1));

    for (int i = 1; i <= N; i++)
    {
        for (int j = 1; j <= M; j++)
        {
            cin >> Board[i][j];
        }
    }

    cout << dfs(1, 1) << "\n";

    for (int i = 1; i <= N;i++)
    {
        for (int j = 1; j <= M; j++)
        {
            cout << dp[i][j] << " ";
        }
        cout << "\n";
    }


    return 0;
}

---