BOGGLEGAME_알고리즘_1

1. 무식하게 풀기

생각

1단계. 먼저 5 x 5 배열에 문자열을 입력받는다.

2단계. 그후 검사할 문자열들을 N개 입력 받는다.

3단계. 입력받은 각 문자열의 문자들이 서로 인접하고 있는지를 판단하는 함수를 호출 true면 YES, false면 NO 출력

함수 내용 

 - bool f(int x,  int y,  char curCharacter) 

 - x 또는 y가 범위 0 <= (x, y) < 5 가 아니라면 false

 - 배열의 [y][x] 인덱스에 있는 문자가 찾아야 할 문자가 아니면 false

 - 해당 인덱스의 문자가 찾는 문자이고 문자열의 길이가 1이라면 true

 - 해당 인덱스의 문자가 찾는 문자이고 문자열의 길이가 1이 아니라면 다음 문자를 인접하는 8방향의 x, y와 다음 문자를 인자로 f함수 재귀 호출

 - 찾는 문자가 문자열의 마지막 문자이면 모두 찾은 것이므로 true

코드

// BOGGLEGAME_1
#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];
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;
                                             
    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;      
    }
    // 현 인덱스의 문자가 찾는 문자가 아니면 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;
            // 현재 검사하려고 하는 문자열의 길이 저장
            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;
}

결과

1
KKKKS
KEEEK
KEYEK
KEEEK
KKKKK
10
YES
YESYES
SYESEY
YESSEY
SYESKSYEY
YESKK
SYESKKY
YESKEY
YESEEY
YESEEEEEEEY
YES YES
YESYES NO
SYESEY NO
YESSEY NO
SYESKSYEY NO
YESKK YES
SYESKKY NO
YESKEY YES
YESEEY YES
YESEEEEEEEY YES

위 방법으로 구하면 최대 

50(최대 테스트 케이스) * 10(문자열의 개수)  * 8^10 (8방향으로 검사하는 것을 글자수만큼 반복 최대 10)

대략 5000억 정도..어마어마하다. 당연 시간초과

이것을 어떻게 줄일 수 있을까.