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

dp와 dfs를 활용한 문제이다. 

 

어떤 착한 조상이 dfs라는 배를 타고 여행을 떠나는데 길을 잘 모르는 상태이다. 그래서 현재 위치(X)를 표시해주고 그 위치에서 갈 수 있는 "A,B,C,D"의 4개의 갈림길을 "A"부터 차례대로 여행을 계속한다. 결국 가고자하는 도착지점에 도착했을 때 아까 체크해주었던 현재 위치(X)로 돌아가고 "B"라는 갈림길로 또 여행을 간다. "D"까지 여행을 다하고 나서 현재 위치(X) 로 돌아온다. 근데 알고봤더니 "A,B,D" 의 갈림길은 도착지점으로 가는 경로였지만 "C"는 낭떠러지였다

 

그래서 착한 조상은 현재 위치(X) 라는 곳에 "A, B, D" 이 세개의 경로만 도착지점에 갈 수 있다고 "3"이라는 숫자를 새겨놓는다. 그 조상은 수많은 여행을 통해 "map[500][500]" 의 지도에 특정 지점에서 도착지점으로 갈 수 있는 경로의 개수를 숫자로 새겨놓았다.

 

이후 젊은 여행자들이 현재 위치(X)에 도착했을 때 착한 조상이 새겨놓은 "3"이라는 숫자를 보고 여기서 도착지점까지 갈 수 있는 길은 3개라는 것을 알 수 있는 것이다.

 

이게 DP 메모이제이션이라는 것이다. 

 

#접근방법 

1. 일반적으로 dfs를 적용을 시키면 되지만 여기서 차이점은 모든 경우의 수를 찾아야하기 때문에 상,하,좌,우 (4가지)에 map은 500*500 이니 최악의 조건시 시간 복잡도는 4^(500*500) 이다. 그렇기 때문에 시간제한 2초를 초과하기 때문에 메모이제이션을 생각을 해야한다. 
2.   dfs를 호출 하면서 방문하지 않았던 구간에 대해서 메모이제이션이 필요하다. 그렇기 때문에 상,하,좌,우 차례대로 들어가면서 도착지점을 만나게 되면 리턴 해준다. 
3. 현재위치에서 "상,하,좌,우"에서 받아온 리턴 값들(경로의 수)을 합해서 현재위치에 숫자로 새긴다. 

* 이번 dfs에서 경사가 낮은쪽으로만 이동하기 때문에 visited 배열을 따로 생성하지 않는다. 즉, 방문 했던 곳은 오르막이기 때문에 거슬러 올라가는일은 없기 때문이다. 

* 이미 방문했던 구역에 dfs가 호출되었다면 그 구역에 적힌 숫자들을 리턴 해주면 된다. 

#include <iostream>
#include <algorithm>
#include <vector>]
#include <cstring>
using namespace std; 
int m, n;
int map[500][500]; 
int v[500][500]; 
int dx[4] = { 0,0,-1,1 }; 
int dy[4] = { 1,-1,0,0 }; 
int dp[500][500]; 
int dfs(int y, int x) {
	if (y == m - 1 && x == n - 1) {
		return 1; 
	}
	int& ret = dp[y][x]; 
	if (ret!=-1)return ret; 
	ret = 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)continue; 
		if (map[ny][nx] >= map[y][x])continue; 
		ret += dfs(ny, nx); 
	}
	return ret; 
}
int main() {
	ios::sync_with_stdio(0); 
	cin.tie(0); 
	cout.tie(0); 
	cin >> m >> n; 
	for (int i = 0; i < m; i++) {
		for (int j = 0; j < n; j++) {
			cin >> map[i][j]; 
			dp[i][j] = -1; 
		}
	}
	//memset(dp, -1, sizeof(dp)); 
	v[0][0] = 1; 
	cout<<dfs(0,0); 
	return 0; 

}

 

1520번: 내리막 길