[백준 1520번] 내리막 길 (C++)

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

1520번: 내리막 길

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
const int MAX = 987654321;

int M, N;
int arr[501][501];
int dp[501][501];

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

int dfs(int y, int x)
{
    if(y==M-1 && x==N-1)  return 1; //무사히 도달한 경우
    if(dp[y][x]!=-1) return dp[y][x]; //이미 방문했으면 해당 값 반환
    dp[y][x]=0; //도달 x
    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) continue; //범위조건
        if(arr[ny][nx] < arr[y][x])
        {
            dp[y][x] += dfs(ny, nx); //카운팅 
        }
    }
    return dp[y][x]; //결과값 반환
}

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

    cin >> M >> N;
    for(int i=0; i<M; i++)
    {
        for(int j=0; j<N; j++)
        {
            cin >> arr[i][j];
            dp[i][j]=-1; //방문처리용
        }
    }

    cout << dfs(0, 0);
    return 0;
}

 

dp + dfs인 문제이다.

시작점인 (0, 0)을 기준으로 맞는 범위 조건하에 상하좌우 4방향을 탐색한다.

현재 값에 다음 값인 상하좌우의 위치가 목표 지점이면 1을 반환하고, 아니면 현재 위치가 끝점이 아니기에 0으로 초기화하고 이어서 상하좌우 4방향을 탐색해준다.

 

계속 이어서 상하좌우 4방향을 탐색하기에 겹치는 부분이 존재한다.

이를 위해 현재 위치의 값이 처음 초기화했던 -1이 아니라면 이미 방문하였다는 뜻이므로 이경우 바로 현재 위치에 담긴 값을 리턴한다.

 

매 위치마다 해당 위치에 대해 4방향을 탐색한 값이 담기게 되고, 이게 누적되어 시작점인 (0, 0) 위치에 담기게 된다.

최종적으로 이를 출력해주면 된다.

 

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

ex) 50 -> 35 -> 30 -> 27 -> 24 -> 22 -> 15 -> 10

10 -> return 1;
10 -> 15 : return 1;
15 -> 22 : return 1;
22 -> 24 : return 1;
24 -> 27 : return 1;
27 -> 30 : return 1;
30 -> 35 : return 1;
35 -> 50 : return 1;

-> 50 / dp[0][0]에 1 누적