[algospot] JUMPGAME 외발 뛰기

외발 뛰기 (ID : JUMPGAME)

---

내 풀이 코드 ( 완전 탐색 일 경우)

#include <iostream>
#include <cstdio>
#include <vector>
using namespace std;
#define MAX 100
// JUMPGAME 완전 탐색

int board[MAX][MAX];
int n;

bool jump(int y, int x){
	// 기저 사례 : 범위 벗어날 때
	if(y < 0 || y >= n || x < 0 || x >= n) return false;
	
	// 맨 끝이면 종료
	if(y == n - 1 && x == n - 1) return true;
	
	return jump( y + board[y][x], x) || jump(y, x + board[y][x]);
}

int main(){
	int C;
	
	cin >> C;
	cin.ignore();
	
	while(C--){
		cin >> n;
		cin.ignore();
		for(int i = 0; i < n; i++){
			for(int j = 0; j < n; j++) cin >> board[i][j];
			cin.ignore();
		}
		if(jump(0, 0)) cout << "YES" << endl;
		else cout << "NO" << endl;
	}
	
}

문제의 간단한 해법

: $$jump(y,x) = jump(y + board[y][x], x) || jump(y, x + board[y][x])$$

내 풀이 코드 (메모이제이션 적용하기)

원하는 답이 존재하는가? 라는 질문을 완전 탐색으로 구할 때 흔히 가장 문제가 되는 것은 , 원하는 답은 없는데 전체 답의 개수는 무지막지하게 많은 경우입니다. 

이 문제에서 최악의 경우가 주어졌을 때, 경로는 n 에 대해 지수적으로 늘어나므로 n = 100 이면 주먹구구를 근거로 시간 제한을 초과하겠지만, 비둘기 집의 원리로 중복 되는 문제가 있다는 것 또한 알 수 있습니다. 또한, jump 는 참조적 투명 함수이기에 메모이제이션의 적용이 가능합니다.

#include <iostream>
#include <cstdio>
#include <vector>
#include <cstring>
using namespace std;
#define MAX 100
// JUMPGAME 메모이 제이션

int board[MAX][MAX];
int cache[MAX][MAX];
int n;

int jump(int y, int x){
	// 기저 사례 : 범위 벗어날 때
	if(y < 0 || y >= n || x < 0 || x >= n) return 0;
	
	// 맨 끝이면 종료
	if(y == n - 1 && x == n - 1) return 1;
	
	// 메모이제이션
	int& ret = cache[y][x];
	// 이미 계산되었으면 바로 반환
	if(ret != -1) return ret;
	
	return ret = jump(y + board[y][x], x) || jump(y, x + board[y][x]);
}

int main(){
	int C;
	
	cin >> C;
	cin.ignore();
	
	while(C-- > 0){
		cin >> n;
		cin.ignore();
		for(int i = 0; i < n; i++){
			for(int j = 0; j < n; j++) cin >> board[i][j];
			cin.ignore();
		}
		memset(cache, -1, sizeof(cache));
		if(jump(0, 0) == 1) cout << "\nYES" << endl;
		else cout << "NO" << endl;
	}
	
}

레시피 대로 메모이제이션을 잘 구현했다고 생각했으나, 간과한 점이 있었습니다.

cache[MAX][MAX] = {-1} 이라는 초기화 방법이 틀렸던 것이었습니다. 해결법으로는

1. memset 을 이용하여 초기화

2. vector 를 사용하여 한번에 초기화

3. fill 함수를 사용하여 초기화