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

문제

www.acmicpc.net/problem/1520

1520번: 내리막 길

풀이

 처음에는 DP만 이용해서, cache[i][j]에 (i,j) 위치까지 도착할 수 있는 모든 내리막길 경우의 수를 저장하려고 했다.

하지만, 상하좌우로 모두 이동이 가능했기 때문에 이 방법은 실패했다.

 두 번째 생각난 방법은, 최단경로찾기 문제로 해석해서 BFS로 푸는 방법이었다. 

하지만, 시간초과 때문에 이 방법은 실패했다.

 

 최종 방법은, DFS에 DP를 접목한 방법이다. DFS로 탐색하되, DP의 메모리제이션을 접목한 것이다.

cache[i][j] : (i,j) 위치 부터, 맨 왼쪽 맨 아래(도착지점) 까지 갈 수 있는 모든 내리막길 경우의 수 

즉, DFS 탐색과정중에, 이전에 탐색했던 좌표에 다시 도달할 경우, 다시 탐색하지 않고 cache값을 이용해서 경로의 개수를 알아내는 것이다. 

• cache를 -1로 초기화 해주었다. 
  • cache값이 0일 때, 탐색한 적이 없는 좌표가 아니라 탐색해봤는데 경로가 0개더라 라는 뜻이기 때문에 탐색한 적이 없는 좌표를 -1로 구분해주기 위함이다. 
• DFS는 재귀로 구현하였다. 

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int n, m;
int table[501][501];
int cache[501][501];

// U, D, L, R
int dc[4] = { -1,1,0,0 };
int dr[4] = { 0,0,-1,1 };

int dfs(int c, int r) { 
	if (r == n - 1 && c == m - 1) // 목적지에 도착 (끝)
		return 1;
	if (cache[c][r] != -1) // 이전에 방문한적이 있으면, cache return
		return cache[c][r];

	cache[c][r] = 0; // 방문 표시 
	int temp = table[c][r]; 
	for (int i = 0;i < 4;i++) { // 상하좌우
		int nc = c + dc[i];
		int nr = r + dr[i];
		if (nc >= 0 && nc < m && nr >= 0 && nr < n) { 
			if (table[nc][nr] < temp)
				cache[c][r] += dfs(nc, nr);
		}
	}
	return cache[c][r];
}
int main(void) {
	cin >> m >> n;
	fill(&cache[0][0], &cache[500][501], -1); // -1로 초기화

	for (int i = 0;i < m;i++) {
		for (int j = 0;j < n;j++) {
			cin >> table[i][j];
		}
	}
	int answer = dfs(0, 0);
	cout << answer << endl;
	return 0;
}

결과