[백준] 알고리즘 C++ 1520번 - 내리막 길문제

문제

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

1520번: 내리막 길

소스코드

/******************************************************************************

Welcome to GDB Online.
GDB online is an online compiler and debugger tool for C, C++, Python, Java, PHP, Ruby, Perl,
C#, VB, Swift, Pascal, Fortran, Haskell, Objective-C, Assembly, HTML, CSS, JS, SQLite, Prolog.
Code, Compile, Run and Debug online from anywhere in world.

*******************************************************************************/
#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <math.h>
using namespace std;
int dp[501][501];
int arr[501][501];
int dx[4]={-1,0,1,0};
int dy[4]={0,1,0,-1};
int n,m;
int dfs(int y,int x){
    if(y==m-1&&x==n-1){
        return 1;
    }
    if(dp[y][x]==-1){
        dp[y][x]=0;
        for(int i=0;i<4;i++){
            int ny=dy[i]+y;
            int nx=dx[i]+x;
            if(ny<0||ny>=m||nx<0||nx>=n||arr[y][x]<=arr[ny][nx]){
                continue;
            }
            dp[y][x]+=dfs(ny,nx);
        }
    }
    return dp[y][x];
}
int main()
{
    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)<<"\n";
}

해설

먼가 이런문제는 방문여부를 확인해야하고, 문제의 조건이 첫시작지점보다 작은 숫자들만 타고 목적지까지 가는게 문제의 키포인트다. 이런문제들은 dfs나 bfs로 풀 수 있다고 한번 생각해 볼 수 있다.

하지만 dfs로 그냥 풀게되면 모든 경우의 수를 계속해서 시도하기 때문에 방문한 흔적을 남기지 않으면(즉 이 길은 절대 갈 수 없다) 계속해서 같은 지점을 방문하고 다시 되돌아갈 것이다. 그렇다면 우리는 이런 부분을 메모할 수 있는 다이나믹 프로그래밍을 이용하여 문제를 같이 풀어보는 것이다.

 

Dp[i][j] 는 i번째 행일 때 j열을 방문했는지 안했는지 체크하는 것이다.

만약 경로를 제대로 찾아가서 마지막 지점까지 도착하게 된다면 리턴1을 함으로써, 한가지의 경로에 대해 1을 리턴하면서 메모한다.

https://wootool.tistory.com/83 

[백준][1520번][DP] 내리막길

이 분의 블로그 밑에 보시면 메모하는 부분이 자세하게 그림으로 나와있습니다. 이 부분을 참고하시면 될 거 같습니다.

나머지는 dfs로 풀듯이 풀고, 방문한 부분은 메모를 하여 처리하는 것을 배워봤습니다.