[동적계획법, 난이도 중상] 백준 1520번 내리막 길

 

이 문제는 동적계획법과 DFS를 동시에 적용해야 하는 문제이다.

백준 1890번 점프와 접근법은 비슷하다.

https://kimcoder.tistory.com/47

[동적계획법, 난이도 상] 백준 1890번 점프

 

경로벡터를 이용하였으며 도착점부터 시작점까지 역으로 DFS를 수행하였다.

자세한 설명은 위 링크에 있는 백준 1890번 점프 풀이를 읽고오면 된다.

아래 그림도 백준 1890번 점프에서 도식화 했던 원리랑 똑같다.

문제에 따른 push_back 기준만 다를 뿐이다.

탐색한 좌표가 맵을 벗어나지 않으면서 자신의 높이보다 더 낮은 경우 이동 할 수 있다.

맵 전체에 for문을 돌려서 동서남북 모두 탐색하면 되는데, 도착점부터 역으로 DFS를 수행할 것이기 때문에 간선의 방향은 반대로 해준다.

 

 

이 문제는 DFS로만 풀면 시간초과라는 벽에 막힌다.

맵 크기는 500x500인데 동서남북 모두 신경 써야하고... 재방문해도 거기서 또 DFS를 호출해야하니 당연히 시간초과가 날 수 밖에 없다.

 

#include <iostream>
#include <algorithm>
#include <string.h>
#include <vector>
#include <queue>
#include <stack>
#include <string>
using namespace std;
int d[501][501];
vector<pair<int, int> > a[501][501];
int map[501][501];
int dx[4] = { 1,-1,0,0 };
int dy[4] = { 0,0,-1,1 };
int n, m;
int dfs(int x, int y) {
	if (x == 0 && y == 0) {
		return 1;
	}
	if (d[x][y] == -1) {
		d[x][y] = 0;
		for (int i = 0; i < a[x][y].size(); i++) {
			int x2 = a[x][y][i].first;
			int y2 = a[x][y][i].second;
			d[x][y] += dfs(x2, y2);
		}
	}
	return d[x][y];
}
int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	cin >> n >> m;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			cin >> map[i][j];
		}
	}
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			for (int k = 0; k < 4; k++) {
				if (i + dx[k] < 0 || j + dy[k] < 0 || i + dx[k] >= n || j + dy[k] >= m)	continue;
				if (map[i][j] < map[i + dx[k]][j + dy[k]]) {
					a[i][j].push_back(make_pair(i + dx[k], j + dy[k]));
				}
			}
		}
	}
	memset(d, -1, sizeof(d));
	int ans;
	ans = dfs(n-1, m-1);
	cout << ans;
}

 

 

+ 2021-09-26 숏코딩 추가 (백준 숏코딩 상위 2.4%)

#include <iostream>
using namespace std;
int map[501][501];
int dp[501][501];
bool v[501][501];
int dx[4]={1,-1,0,0};
int dy[4]={0,0,-1,1};
int n,m,e,fx,fy,ans;
int dfs(int x, int y){
	if(x==n-1&&y==m-1) return 1;
	for(int k=0;k<4;k++){
		fx=x+dx[k];
		fy=y+dy[k];
		if(fx<0||fx>=n||fy<0||fy>=m) continue;
		e=map[fx][fy];
		if(e<map[x][y]){
			if(v[fx][fy]) dp[x][y]+=dp[fx][fy];
			else dp[x][y]+=dfs(fx,fy);
		}
	}
	v[x][y]=true;
	return dp[x][y];
}
int main() {
	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);
}