[BOGGLE] 보글게임

[BOGGLE] 보글 게임 : https://algospot.com/judge/problem/read/BOGGLE?c=16921

### DP ###

check(i, j, word) : (i, j) 에서 문자열 word 를 만들수 있는지. 

<소스코드>

#include <cstdio>
#include <cstring>
#include <string>
#include <map>
using namespace std;
 
char boggle[5][6];
int di[]={1, 1, 0, -1, -1, -1, 0, 1};
int dj[]={0, 1, 1, 1, 0, -1, -1, -1};
 
int sNum = 1;
map<string, int> msi;
int d[5][5][10000];
 
int check(int curI, int curJ, char *word)
{
    if(*(word+1) == 0) return true;
 
    int num;
    if(msi.find(word) == msi.end()) {
        msi[word] = sNum;
        num = sNum++;
    }
    else num = msi[word];
    
    int &ret = d[curI][curJ][num];
    if(ret != 0) return ret;
 
    for(int k=0; k<8; k++) {
        int nextI = curI+di[k];
        int nextJ = curJ+dj[k];
        if((0 <= nextI && nextI < 5) && (0 <= nextJ && nextJ < 5)) {
            if(boggle[nextI][nextJ] == *(word+1) && check(nextI, nextJ, word+1) == 1)
                return ret = 1;
        }
    }
    return ret = -1;
}
 
bool BOGGLE(char *word)
{
    for(int i=0; i<5; i++)
        for(int j=0; j<5; j++)
            if(boggle[i][j] == *word && check(i, j, word) == 1)
                return true;
    return false;
}
 
int main()
{
    int tc;
    scanf("%d", &tc);
 
    while(tc--) {
        for(int i=0; i<5; i++)
            scanf("%s", boggle[i]);
        
        memset(d, 0, sizeof(d));
 
        int n;
        scanf("%d", &n);
        while(n--) {
            char word[11];
            scanf("%s", word);
            printf("%s ", word);
            BOGGLE(word) ? puts("YES") : puts("NO");
        }
    }
}    

>> 완전 탐색으로 소개되는 문제지만, 시간초과가 난다.

>> 해결방법은 DP 라는데... 

>> 문자열을 메모이제이션 할 방법이 도무지 떠오르질 않아 푸는데 오래 걸렸던 문제..!! >> 해싱으로 처리하였다.