C++ [Algorithm] - 백준 1520 내리막길

문제

---

입출력

---

문제 요약

(0,0)으로 시작해서 (m,n)까지 갈 수 있는 경로를 구하는 문제이다.

단 이동할 수 있는 조건은 다음 좌표의 위치값이 현재 좌표의 위치값보다 작아야한다.

이 조건은 dfs 함수에서 (map[x][y] > map[nx][ny])로 구현하면 될 것 같다.

 

모든 경로의 수를 구해야 하니 살짝 dp 메모제이션 기법을 사용하면 좋을 것 같다.

 

[dp 배열]

3	2	2	2	1
1			1	1
1			1
1	1	1	1	목적지

 

문제에서 주어진 모든 경로들이 지나가는 곳에 1씩 더하면서 dfs를 시작하면

최종적으로 이런 dp 배열 형태가 만들어질 것이다.

---

코드

#include <iostream>
#include <cstring>

using namespace std;

int map[501][501];
int visited[501][501];
int dx[4] = { -1, 0, 1, 0 };
int dy[4] = { 0, 1, 0, -1 };
int N, M;

int dfs(int x, int y) {

    if (x == N - 1 && y == M - 1) {
        return 1;
    }

    if (visited[x][y] == -1) {
        visited[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){
                if (map[x][y] > map[nx][ny]) {
                    visited[x][y] += dfs(nx, ny);
                }
            }
        }
    }

    return visited[x][y];
}

int main() {

    cin >> N >> M;

    memset(visited, -1, sizeof(visited));

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

    cout << dfs(0, 0) << endl;

    return 0;

}