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");
}
}
}
