이것 저것 &

문제링크:www.acmicpc.net/problem/1520

dp라는걸 모르고 풀었음 더 어려웠을 문제였습니다. 
처음에 bfs 관점으로 접근하는데 자꾸 예외케이스가 생겼습니다.

예를 들어서, 단순히 오른쪽, 아래로만 이동하는게 아니라 위에 올라갔다가, 왼쪽으로 갔다가 올 수도 있기 때문입니다.

 
그래서 모든 경우를 탐색해주어야 한다고 인식하게 되었고, dp의 UP-DOWN 방식으로 구현을 하자는 아이디어를 얻었습니다.

점화식은 아래처럼 구현했습니다. 이때 ny, nx는 인접한 4방향 좌표를 모두 탐색합니다.

if (ny >= 1 && ny <= m && nx >= 1 && nx <= n) {
			if (arr[y][x] < arr[ny][nx]) {
				ret += solved(ny, nx);
			}
		}

아래는 전체 정답코드입니다.

#include <iostream>
#include <cstring>
using namespace std;
/*
	dp라고 모르고 풀었음 더 어려웠을 문제
	처음에 bfs 관점으로 접근하는데 자꾸 예외케이스가 생김
	모든 경우를 탐색해주어야 한다고 인식하게 됨 -> UP-DOWN 방식으로 구현
*/
int m, n;
int arr[501][501] = { 0, };
int dp[501][501] = { 0, };

int y_ar[4] = {0, 0, -1, 1};
int x_ar[4] = { 1,-1,0,0 };

int solved(int y, int x) {
	if (y == 1 && x == 1)
		return 1;
	int &ret = dp[y][x];
	if (ret != -1) return ret;
	ret = 0;

	for (int i = 0; i < 4; i++) {
		int ny = y + y_ar[i];
		int nx = x + x_ar[i];
		if (ny >= 1 && ny <= m && nx >= 1 && nx <= n) {
			if (arr[y][x] < arr[ny][nx]) {
				ret += solved(ny, nx);
			}
		}
	}

	return ret;
}

int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0), cout.tie(0);

	cin >> m >> n;

	for (int i = 1; i <= m; i++)
		for (int j = 1; j <= n; j++)
			cin >> arr[i][j];

	memset(dp, -1, sizeof(dp));
	cout << solved(m,n) << endl;

	/*
	for (int i = 1; i <= m; i++) {
		for (int j = 1; j <= n; j++)
			cout << dp[i][j] << ' ';
		cout << endl;
	}
	*/
	return 0;
}

dp라고 인식되는  순간 체감난이도가 확 줄었습니다.

이해가 안되시면 천천히 디버깅해보세요!

문제링크:https://www.acmicpc.net/problem/1520

어려운 문제였습니다. 기존 dp와는 많이 달라서 저도 해맸습니다. ㅠㅠ

우선 문제를 보자마자 완전탐색문제구나 인식하실 수 있습니다.

이때 n=500, m=500 까지 가능합니다.  일반적인 dfs, bfs로 푸실 경우

최악의 경우에는 4^500*500 번까지 연산이 진행되기 때문에 일반적인 방법으로는 풀 수 없었습니다.

답은 dp적인 관점으로 기존에 탐색한 경로의 값을 가지고, 해당 좌표에 방문하면 해당값을 반환하는 형태로 dfs를 구현하는 것입니다. 즉 dp의 up-down 방식과 dfs 방식을 합쳐서 답을 구해야 합니다. 

즉 깊이 우선 탐색을 하면서 탐색한 값을 이전 함수에 전달해주면서 결과 값을 도출합니다.

도착지에 도착하면 그 이전함수에 값들을 전달해주면서 더해주어 dp[1,1]에서 결과값을 찾는 것 입니다.

우선 해당관점을 생각하는거 자체가 어렵고, 구현난이도는 높지않습니다.

int dfs(int cy, int cx) {

	if (cy == m  && cx == n) {
		//dp[cy][cx] = 1;
		return 1; //종점이라면 1을 반환합니다. 
	}
	if (dp[cy][cx]) //이미 방문한 곳이라면 해당 dp값을 전달해준다.
		return dp[cy][cx];

	for (int i = 0; i < 4; i++) {
		int next_y = cy + y_ar[i];
		int next_x = cx + x_ar[i];

		if (next_y > 0 && next_y <= m && next_x > 0 && next_x <= n)
			if (arr[cy][cx] > arr[next_y][next_x]) 
				dp[cy][cx] += dfs(next_y, next_x); 
		
	}
	return dp[cy][cx];
}

 1. 출발점에서 dfs를 시작해서 종점에 도착하면 1을 반환한다.

 2. 만약 이미 방문한 곳이라면 탐색하지 않고 기존값을 전달합니다. 

 3. 두 경우가 아니라면 상하좌우를 탐색하며 해당 좌표로 이동할 수 있는지 확인하여 줍니다.

위 식에서 한가지 간과하게 있습니다. 만약 dp값이 0이여도 이미 탐색한 경우했을 수 있다는 것을 간과했습니다. 따라서 visited 배열을 하나더 만들어서 방문했는지 여부를 따로 판단해주어야 합니다. 

아래는 정답코드입니다.

#include <iostream>
using namespace std;
int arr[501][501]= {};
int dp[501][501] = {};
bool visited[501][501] = { 0 };
int m, n;
int y_ar[4] = { 1, 0, -1, 0 };
int x_ar[4] = { 0, 1, 0, -1 };

int dfs(int cy, int cx) {

	
	if (cy == m  && cx == n) {
		//dp[cy][cx] = 1;
		return 1; //종점이라면 1을 반환합니다. 
	}
	if (visited[cy][cx]) //이미 방문한 곳이라면 해당 dp값을 전달해준다.
		return dp[cy][cx];
	visited[cy][cx] = 1;
	for (int i = 0; i < 4; i++) {
		int next_y = cy + y_ar[i];
		int next_x = cx + x_ar[i];

		if (next_y > 0 && next_y <= m && next_x > 0 && next_x <= n)
			if (arr[cy][cx] > arr[next_y][next_x]) 
				dp[cy][cx] += dfs(next_y, next_x); 
		
	}
	return dp[cy][cx];
}

int main() {
	cin.tie(NULL);
	ios::sync_with_stdio(false);

	cin >> m >> n;
	for (int i = 1; i <= m; i++)
		for (int j = 1; j <= n; j++)
			cin >> arr[i][j];
	
	
	cout << dfs(1, 1)<< '\n';
	return 0;	
}

걍 문제자체가 어려웠습니다.. 코드를 보고도 설명이 이해가 가지 않으신다면 아래 링크를 참고해보세요.

https://wootool.tistory.com/83