[백준]1520번: 내리막 길

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

1520번: 내리막 길

이거... 나한테는 너무 어려웠다...

 

오래 고민하고 힌트 봐도 잘 모르겠어서 다른 분들 풀이를 아주 많이 참고했음

 

다른 분들 풀이 볼때에도 이해하는 데 좀 오래 걸렸당...ㅎ

 

---

 

결론부터 말하자면 이 문제는 dfs + dp 문제다

 

 

현재 칸으로부터 도착점까지 이동하는 경로의 수는 인접한 칸(상하좌우, 최대 4개)을 시작점으로 도착점까지 이동하는 경로의 수들의 합이다.

 

각 칸을 시작점으로 도착점까지 이동할 수 있는지 여부는 dfs로 확인한다.

특정 칸을 시작점으로 dfs를 수행했을 때, 탐색은 (1)더이상 방문할 칸이 없거나, (2)도착점에 도달할 경우 종료된다.

 

따라서 (0,0)을 시작점으로 dfs를 재귀적으로 구현하면 풀 수가 있다.

---

그런데 이 문제에서는 단순 dfs로 풀면 시간이나 메모리 초과가 날거다!!

 

그래서 동적 계획법을 이용해야한다.

모든 칸에서 dfs를 수행하여 경로의 개수를 구할 때마다 그 결과를 저장해둔다면,

탐색 중 값이 저장되어 있는 칸을 만날 때마다 매번 탐색을 새로 수행할 필요가 없고, 저장해둔 값을 가져오기만 하면 된다.

이렇게 하면 불필요한 연산을 줄일 수 있따

 

---

#include <iostream>
int m,n;
int graph[500][500]; //지도
int dp[500][500]; //경로 수 저장할 배열

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

using namespace std;

int dfs(int x, int y){
    if(x==m-1 && y==n-1) return 1; //도착점에 도달
    if(dp[x][y]!=-1) return dp[x][y]; //방문한 적이 있으면 저장된 값을 리턴
    
    dp[x][y]=0; //방문 처리
    
    for(int i=0;i<4;i++){ //상하좌우로 인접한 칸 방문
        int nextX=x+dx[i];
        int nextY=y+dy[i];
        if(nextX>=0 && nextX<m && nextY>=0 && nextY<n){ //x,y 범위 체크
            if(graph[x][y] > graph[nextX][nextY]){ //높이 조건 체크
                dp[x][y] += dfs(nextX,nextY); //탐색 수행
            }
        }
    }

    return dp[x][y];
    
}

int main()
{
    cin>>m>>n;
    for(int i=0;i<m;i++){
        for(int j=0;j<n;j++){
            cin>>graph[i][j];
            dp[i][j]=-1; //방문하지 않았다는 의미로 모두 -1로 초기화
        }
    }
    
    cout<<dfs(0,0);

    return 0;
}