16) 백준 1520 - 내리막 길

1520번: 내리막 길 (acmicpc.net)

1520번: 내리막 길

---

시간이 생각보다 좀 걸렸던 문제...

DFS와 Memoization을 사용했던 문제인데 2년 전에 공부한 것을 다 까먹었다..ㅠㅠㅠ

#include <bits/stdc++.h>

using namespace std;

int x_p[4] = {0, 1, 0, -1};
int y_p[4] = {1, 0, -1, 0};
int road[500][500];
int memo[500][500];

int M, N;

int dfs(int x, int y) {
	if(x == M-1 && y == N-1) {
		return 1;
	}
	if(memo[x][y] != -1) {
		return memo[x][y];
	}
	memo[x][y] = 0;
	for(int i = 0; i < 4; i++) {
		int tx = x + x_p[i];
		int ty = y + y_p[i];
		if(tx < M && ty < N && tx >= 0 && ty >= 0
		&& road[x][y] > road[tx][ty]) {
			memo[x][y] = memo[x][y] + dfs(tx, ty);
		}
	}
	return memo[x][y];
}

int main(void) {
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	cin >> M >> N;
	
	for(int i = 0; i < M; i++) {
		for(int j = 0; j < N; j++) {
			cin >> road[i][j];
			memo[i][j] = -1;
		}
	}
	
	cout << dfs(0, 0);
}

처음에는 그냥 DFS만 사용하려 했지만 시간초과로 어떤 방법이 있을까 고민하던중 같은 곳을 계속 반속해서 가는 경우가 있다는 것을 알아차렸다. 그래도 아이디어가 떠오르지 않았는데 티스토리에 기록한게 있나 하고 보니 Memoization를 발견해서 시도해봤다.

 

처음에는 memo(Memoization을 사용하는 배열)을 0으로 초기화 했더니 게속 36%에서 실패했다. 그리고 -1로 바꿔주니 성공했다. 

 

0으로 초기화 하면 안되는 이유는 "갈 수 없는 곳"과 "한번도 지나가지 않은 곳"을 구분해주기 위함이다.

따라서 아직 지나지 않은 곳은 -1로, 갈 수 없는 곳은 0으로 기록하여 문제를 풀어야한다.

 

당분간 Memoization을 공부해야겠다...ㅠㅜㅠㅠ