백준 1520 C++

백트래킹으로 시도하다가 시간초과 나서 다른 분들의 코드를 보았다.!

 

문제

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

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

 

 

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

20의 지점은 재방문된다. 이떄 재방문되는 지점이 많아지면 많아질수록 시간초과가 발생한다.

DFS + DP를 사용해서 풀어야 한다.

 

그래서 재방문되는 지점은 DP를 통해 경로의 수를 저장해주어야 한다.

#include <iostream>
#include <vector>
using namespace std;
int n,m;
int dp[501][501];
bool visited[501][501];
int dx[4] = {0,0,-1,1};
int dy[4] = {1,-1,0,0};
int map[501][501];
 
int dfs(int x,int y){
 
   if(x == n-1 && y == m-1){ //맨 끝 좌표일떄 1리턴
       return 1;
   }
 
    
    if(visited[x][y] == false){
        visited[x][y] = true;
    
    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(map[nx][ny] < map[x][y]){
           dp[x][y] = dp[x][y] + dfs(nx,ny);
        }
 
    }
    }
    return dp[x][y];
    
    
}
 
int main(void){
    cin >> n >> m;
    for(int i = 0;i<n;i++){
        for(int j = 0;j<m;j++){
            cin >> map[i][j];
        }
    }
 
    cout << dfs(0,0);
}