BOGGLEGAME_알고리즘_3

3. 중첩으로 저장하는 부분 제외하기 

생각

기본적인 원리는 [BOGGLEGAME_알고리즘_1]과 동일하다. 

하지만 조금 깊게 생각해보면 8방향을 검사할때 중첩되는 부분이 있다는 것을 알 수 있다.

예를 들면 

0  1  2

3  4  5

6  7  8

일때 

이런식으로 갈수 있는 방향을 트리로 정리할 수 있다. 

이때 트리의 깊이가 단어의 길이라고 생각하면 붉은 원 두개가 서로 같은 정보를 가지고 있는 것을 알 수 있다. 

이 알고리즘의 핵심은 이 붉은 부분을 검사한 후 그 결과값을 저장해 놓는다는 것에 있다.

즉, 단어의 4번째 글자를 찾기 위해 재귀적으로 검사할때 

0번으로 들어가서 검사할 수 있는 위 3개(1, 3, 4)의 각 요소에 찾는 알파벳이 없다면 

더이상 4번째 글자를 찾기 위해 0번으로 들어가 일일이 확인해 볼 필요가 없다는 것이다. 

위의 아이디어를 구현하기위해 필요한 코드는 의외로 간단하다.

기존의 코드에 캐시를 저장할 수 있는 배열을 만들어놓고, 위와 같은 상황이 되면 -1로 표시하는 부분만 구현하면 된다.

코드

// BOGGLEGAME_2
#include <iostream>
#include <string.h>
static const int BOGGLE_MAX = 5;
static const int WORD_MAX = 10;
int g_ArrX[] = { -1, 0, 1, 1, 1, 0, -1, -1 };
int g_ArrY[] = { -1, -1, -1, 0, 1, 1, 1, 0 };
char* g_Boggle[BOGGLE_MAX];
char* g_WordsArr[WORD_MAX];
// 기록 배열
char g_CacheArr[BOGGLE_MAX][BOGGLE_MAX][WORD_MAX] = {0,};
int g_StringLen = 0;
int g_CurCharNum = 0;
int g_CurWordNum = 0;
// 해당 좌표에 전달되는 문자가 있는지 검사
bool f(int y, int x, char CurChar)
{
    // 기저사례 1 x또는 y가 범위 밖이라면 false
    if (x < 0 || y < 0)
        return false;
    
    // 기저사례 1 x또는 y가 범위 밖이라면 false
    if (x >= BOGGLE_MAX || y >= BOGGLE_MAX)
        return false;
    
    // 기저사례 2 찾으려는 문자가 '\0' 이거나
    // 문자열의 길이와 같으면 문자열을 찾은것이므로 true
    if (CurChar == '\0' || g_CurCharNum > g_StringLen)
        return true;
    
    // 찾으려고 하는 좌표가 이미 -1 이라면 여긴 이전에 찾았던 곳이므로 패스
    if (g_CacheArr[y][x][g_CurCharNum] == -1)
        return false;
    
    if (g_Boggle[y][x] == CurChar)
    {
        if (g_StringLen == 1){
            // 기저사례 3 문자를 찾았는데 문자열의
            // 길이가 1이면 곧 찾는 문자열이므로 true
            return true;
        }
        // 문자를 찾았으면 문자인덱스를 1증가
        ++g_CurCharNum;
        // 현 인덱스를 중심으로 다음 문자를 8방향 검사
        for (int i = 0; i < 8; i++)
        {
            // 모두 찾으면 true
            if (f(
                  (y + g_ArrY[i]), // y좌표
                  (x + g_ArrX[i]), // x좌표
                  g_WordsArr[g_CurWordNum][g_CurCharNum])
                )
            {
                return true;
            }
        }
        // 문자를 못찾았으면 문자인덱스 1감소
        --g_CurCharNum;
        
        // 8방향 모두 아니라면 현재 좌표에서 다음문자를 찾을 방법이 없기때문에 -1
        g_CacheArr[y][x][g_CurCharNum] = -1;
    }
    // 현 인덱스의 문자가 찾는 문자가 아니면 false
    return false;
}
 
int main()
{
    // 테스트 케이스
    int testCase = 0;
    int stringCount = 0;
    int temp = 0;
    for (int i = 0; i < BOGGLE_MAX; i++)
    {
        g_Boggle[i] = new char[BOGGLE_MAX + 1]();
    }
    for (int i = 0; i < WORD_MAX; i++)
    {
        g_WordsArr[i] = new char[WORD_MAX + 1]();
    }
    scanf("%d", &testCase);
    while (testCase--){
        g_CurWordNum = 0;
        
        // 보글게임판 5 x 5 입력
        for (int i = 0; i < BOGGLE_MAX; i++)
        {
            scanf("%s", g_Boggle[i]);
        }
        // 확인하려는 문자열 갯수 입력
        scanf("%d", &stringCount);
        temp = stringCount;
        // 확인하려는 문자열 입력  ENTER 구분
        for (int i = 0; i < stringCount; i++)
           {
            scanf("%s", g_WordsArr[i]);
        }
        while (stringCount--){
            bool isYes = false;
            // 단어를 찾는 루프를 돌 때마다 캐시를 -1로 초기화해준다.
            memset(g_CacheArr, 0, sizeof(g_CacheArr));
            // 현재 검사하려고 하는 문자열의 길이 저장
            g_StringLen = (int)strlen((const char*)g_WordsArr[g_CurWordNum]);
            // g_CurCharNum = 현재 검사하려고하는 문자 인덱스 예) ABCDE에서 C 면 2
            g_CurCharNum = 0;
            for (int y = 0; y < BOGGLE_MAX; y++)
            {
                for (int x = 0; x < BOGGLE_MAX; x++)
                {
                    // y, x인덱스와 찾으려는 문자열의 문자를 f에 넘김
                    // 있으면 YES
                    if (
                        f(y,
                          x,
                          g_WordsArr[g_CurWordNum][g_CurCharNum]))
                    {
                        printf("%s YES\n", g_WordsArr[g_CurWordNum++]);
                        isYes = true;      // 루프를 빠져나간다.
                        break;              // 루프를 빠져나간다.
                    }
                }
                if (isYes)               // 루프를 빠져나간다..
                    break;                   // 루프를 빠져나간다..
            }
            
            // 4, 4까지 돌았는데 없으면 NO
            if (!isYes)
            {
                printf("%s NO\n", g_WordsArr[g_CurWordNum++]);
            }
        }
    }
    
    // 메모리 해제
    for (int i = 0; i < BOGGLE_MAX; i++)
    {
        delete []g_Boggle[i];
        g_Boggle[i] = NULL;
    }
    for (int i = 0; i < WORD_MAX; i++)
    {
        delete[]g_WordsArr[i];
        g_WordsArr[i] = NULL;
    }
    return 0;
}

총 4곳이 수정되었다.(main 1 + 함수 3)

1. 첫번째는 캐시 배열을 선언하는 부분

// 캐시 배열
char g_CacheArr[BOGGLE_MAX][BOGGLE_MAX][WORD_MAX] = {0,};

2. 둘째는 현재 좌표가 -1(이전에 찾아본 곳)일 경우 false를 반환하는 부분

// 찾으려고 하는 좌표가 이미 -1 이라면 여긴 이전에 찾았던 곳이므로 패스
if (g_CacheArr[y][x][g_CurCharNum] == -1)
    return false;

3. 셋째는 8방향이 모두 아니라면 -1로 마킹하는 부분이다.

// 8방향 모두 아니라면 현재 좌표에서 다음문자를 찾을 방법이 없기때문에 -1
g_CacheArr[y][x][g_CurCharNum] = -1;

4. 넷째는 캐시 배열을 초기화 하는 부분이다.(main)

while(StringCount--) 이후에 추가된다.

// 단어를 찾는 루프를 돌 때마다 캐시를 -1로 초기화해준다.
memset(g_CacheArr, 0, sizeof(g_CacheArr));

결과

1
AAAAA
AAAAA
AAAAA
AAAAA
AAAAA
5
AAAAAAAAAAD
AAAAAAAAAAD
AAAAAAAAAAD
AAAAAAAAAAD
AAAAAAD
AAAAAAAAAAD NO
AAAAAAAAAAD NO
AAAAAAAAAAD NO
AAAAAAAAAAD NO
AAAAAAD NO

이로써  BOGGLEGAME문제를 해결할 수 있었다. 

시간은 6ms가 나왔다.