ALGOSPOT - BOGGLE

문제

https://algospot.com/judge/problem/read/BOGGLE

풀이

동적 계획법 문제같아서 동적 계획법으로 풀었다. 그래프로 풀 수 있지 않을까라는 생각이 들지만 나는 DP로만 풀었으므로 DP 풀이만 적음.

먼저 findAll()과 solve() 두개의 함수를 작성했다. findAll()은 좌표 [0,0]부터 [4,4]까지, 즉 모든 칸에서 입력받은 문자열을 찾을 수 있는지 확인하는 solve()를 실행시키는 함수이다.

solve함수는 세개의 인자를 받는데 각각 게임판의 y좌표, x좌표, 게임판의 y,x 좌표의 문자열과 비교할 찾을 문자열의 index번째 문자다.

메모이제이션은 dp[y][x][index] = 게임판[y][x] 좌표에서 시작해 word[index] 이후의 문자들을 매칭 시킬수 있는가에 대해 메모이제이션을 적용했다. 입력값이 작아서 최대 250크기 만큼의 배열만 사용하므로 3차원 배열을 사용해도 문제가 없었다.

#include <cstdio>
#include <cstring>
char map[5][6],word[11];
int dp[5][5][10];
int solve(int y, int x, int index){
	int i,j;
	//메모이제이션 값 체크. 초기값 -1이 아니라면 바로 리턴
	int& ret = dp[y][x][index];
	if(ret != -1) return ret;
	for(i=-1;i<=1;i++){
		for(j=-1;j<=1;j++){
			//인접한 칸을 검사하며 게임판을 벗어났다면 패스한다.
			if((i==0&&j==0)||y+i<0||y+i>4||x+j<0||x+j>4) continue;

			//매칭되는 문자열을 찾았을때
			if(map[y+i][x+j] == word[index]){
				//다음 문자가 null이라면 즉, 모든 문자를 다 찾았다면 true를 반환한다.
				if(word[index+1] == '\0') return ret = 1;
				//아직 다 찾지 못했으므로 현재 위치에서 시작하는 다음 문자를 찾는 함수를 재귀 호출한다.
				ret = solve(y+i,x+j,index+1);
				//만약 현재 위치에서 문자열 매칭에 성공했다면 더 찾을 필요가 없으므로 바로 1를 반환한다.
				if(ret==1) return ret;
			}
		}			
	}
	//여기까지 왔다면 문자를 찾지 못한것이므로 0을 반환한다.
	return ret = 0;
}
int findAll(){
	int i,j;
	for(i=0;i<5;i++){
		for(j=0;j<5;j++){
			int& ret = dp[i][j][0];
			if(ret != -1) return ret;
			if(map[i][j] == word[0]){
				ret = solve(i,j,1);
				if(ret) return ret;
			}
		}
	}
	return 0;
}
int main(){
	int i,j,t,n;
	scanf("%d",&t);
	while(t--){
		for(i=0;i<5;i++)
			scanf(" %s",map[i]);
		scanf(" %d",&n);
		while(n--){
			memset(dp,-1,sizeof(int)*250);
			scanf(" %s",word);
			printf("%s %s\n",word,findAll()?"YES":"NO");
		}
	}
}