백준 - 내리막 길(1520)

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

1520번: 내리막 길

 

DFS + 메모이제이션

 

DFS를 응용해서 

중복된 길에 대한 데이터 처리 기법이다.

다음 이동할 지점이 이미 목적지에 도달할 수 있다는 데이터를 가지고 있으면

굳이 목적지까지 갈 필요가 없다.

 

ex)

 

50 45 37 32 30

49 48 90 20 25

90 90 25 17 28

27 24 22 15 10

 

dp

-1 -1 -1 -1 -1

-1 -1 -1 -1 -1

-1 -1 -1 -1 -1

-1 -1 -1 -1 -1

 

예제를 수정해서 과정을 지켜본다.

dp는 전부 -1로 초기화하고

현재 지점은 dp를 0으로 바꿔준다.

 

DFS를 진행하고 나면

0   0   0  0  0

-1 -1 -1  0  0

-1 -1 -1  0 -1

-1 -1 -1  0 -1

 

목적지는 0으로 바꾸지 않는다.

다시 되돌아갈 때 이동했던 곳의 DP값을 더해주며 이동한다.

0    0   0   -1  -1

-1  -1  -1  -1  -1

-1  -1  -1  -1  -1

-1  -1  -1  -1  -1

 

32까지 되돌아오게 되면

그 아래 20에 갈 수 있었다.

DFS 계속 진행

 

 

0   0   0   -1   -1

-1  -1  -1  0   -1

-1  -1  -1  0   -1

-1  -1  -1  0   -1

 

되돌아오는 과정에서 똑같이 반복한다.

-2  -2  -2  -2  -1

-1  -1  -1  -1  -1

-1  -1  -1  -1  -1

-1  -1  -1  -1  -1

 

-2값을 보면 50, 45, 37, 20이며

해당 부분을 이동 과정 중에 만나면

더 이상 DFS를 진행할 필요 없이 dp를 더해주며 되돌아가면 된다.

 

-2  -2  -2  -2  -1

0    0   -1  -1  -1

-1  -1  -1  -1  -1

-1  -1  -1  -1  -1

 

-4  -2  -2  -2  -1

-2  -2  -1  -1  -1

-1  -1  -1  -1  -1

-1  -1  -1  -1  -1

 

그래서 4라는 개수가 나온다.

 

 

 

#include <iostream>
#include <vector>

using namespace std;
vector<vector<int>> graph;
vector<vector<int>> visited;
void dfs(int y, int x);
int y_next[4] = { 0, -1, 0, 1 };
int x_next[4] = { 1, 0, -1, 0 };
int n, m;

void dfs(int y, int x) {
	
	if (y == n-1 && x == m-1) 
		return;
	
	if (visited[y][x] != -1)
		return;

	visited[y][x] = 0;

	for (int i = 0; i < 4; i++) {
		int cur_y = y + y_next[i];
		int cur_x = x + x_next[i];
		
		if (cur_y < 0 || cur_y >= n || cur_x < 0 || cur_x >= m)
			continue;
		
		if (graph[cur_y][cur_x] < graph[y][x])
		{
			if (visited[cur_y][cur_x] != -1) {
				visited[y][x] += visited[cur_y][cur_x];
			}
			else {
				dfs(cur_y, cur_x);
				visited[y][x] += visited[cur_y][cur_x];
			}
		}
	}

}
int main() {
	
	cin >> n >> m;
	for (int i = 0; i < n; i++) {
		vector<int> temp_vec;
		vector<int> visited_temp(m, -1);
		for (int j = 0; j < m; j++) {
			int temp;
			cin >> temp;
			temp_vec.push_back(temp);
		}
		visited.push_back(visited_temp);
		graph.push_back(temp_vec);
	}
	dfs(0, 0);
	
	cout << visited[0][0] * -1;

}