백준/1520번/내리막길/골드3

Problem Link: https://www.acmicpc.net/problem/1520

문제 설명

Site: Baekjoon
Number: 1520
Category: DFS + Dynamic Programming
Rank: Gold 3

DFS와 DP를 혼합하여 해결하는 문제이다.

DFS만으로 진행한다면 가능한 경로의 수가 10억이 넘기 때문에 시간초과가 발생한다.

DP배열을 두어 해당 좌표까지의 값을 지속적으로 갱신하여 해결하면 된다. (*풀이에서 dp배열의 이름은 path이다.)

path배열의 도착 지점의 값은 1로 설정하고, DFS를 진행하며 -1인 경우 아직 탐색이 안되었다는 의미이니 탐색, 0이라면 탐색을 진행하였지만 경로가 없다는 의미로 탐색을 진행하지 않는다.

path배열의 값은 자기 자신에서 갈 수 있는 4방향을 탐색하여 탐색이 가능하다면 DFS를 통해 값을 입력하여 값을 누적하고, 최종적으로 모든 경로의 값이 path[0][0]에 저장되게 한다.

#include <iostream>
#include <vector>

using namespace std;

int N, M;

//좌상우하 순 방향 배열
int dirx[4] = { 0, -1, 0, 1 };
int diry[4] = { -1, 0, 1, 0 };

int DFS(int x, int y, vector<vector<int>>& v, vector<vector<int>>& path)
{
    //path가 -1보다 크다는 의미는 탐색한 기록이 있다는 의미로 더이상 탐색할 필요가 없으니 저장된 값을 return한다
    if (path[x][y] > -1)
        return path[x][y];

    //기존 path값은 -1로 탐색을 진행하였으니 0으로 바꾸어준다
    path[x][y] = 0;

    for(int i = 0; i < 4; i++)
    {
        int newx = x + dirx[i];
        int newy = y + diry[i];

        //배열 범위를 벗어나는 경우
        if (newx < 0 || newx > N - 1 || newy < 0 || newy > M - 1)
            continue;

        //값이 줄어들지 않거나, 이미 탐색을 진행하였지만 값이 0, 즉 경로가 없는 경우
        if (v[x][y] <= v[newx][newy] || v[newx][newy] == 0)
            continue;

        //탐색이 가능하다면 거기서 갈 수 있는 경로의 값을 누적해서 저장한다.
        path[x][y] += DFS(newx, newy, v, path);
    }

	return path[x][y];
}

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

    cin >> N >> M;

    vector<vector<int>> v(N, vector<int>(M, 0));
    vector<vector<int>> path(N, vector<int>(M, -1));

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

    path[N - 1][M - 1] = 1;
    cout << DFS(0, 0, v, path);

    return 0;
}