ID: BOGGLE 난이도: 하 (재귀 완전탐색)(매우느림)

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

재귀를 이용한 완전탐색을 하여서 속도가 매우 느림

차후에 재귀가 아닌 방법으로 다시 풀이해야함.

#include <iostream>
#include <string>
#include <vector>
 
 
class Word {
public:
    struct bundle{
        std::string sWord;
        std::string sHasWord;
    };
    //Word() { cWord = ""; cExist = false; }
    std::vector<bundle> cWordVec;
};
 
class Bogle {
public:
    const int dx[8] = {-1, -1, -1, 1, 1, 1, 0, 0};
    const int dy[8] = { -1, 0, 1, -1, 0, 1, -1, 1 };
    Bogle() { cWord.cWordVec.clear(); }
    Word cWord;
    std::string cBogle[5];
 
    void CheckWord();
 
private:
 
    bool HasWord(int x, int y, const std::string& word);
    bool inRange(int x, int y);
};
 
int main()
{
    int nCaseNum;
    int nWordNum;
 
    
    std::vector<Bogle> nBogleList;
    //std::vector<Word> nWord;
    //std::vector<std::vector<Word>> nWordList;
        
    nBogleList.clear();
    std::cin >> nCaseNum;
    getchar();
 
    for (int i = 0; i < nCaseNum; ++i)
    {
        Bogle bogle;
        std::getline(std::cin, bogle.cBogle[0]);
        std::getline(std::cin, bogle.cBogle[1]);
        std::getline(std::cin, bogle.cBogle[2]);
        std::getline(std::cin, bogle.cBogle[3]);
        std::getline(std::cin, bogle.cBogle[4]);
        
    /*    bogle.cBogle[0] = "AEPLC";
        bogle.cBogle[1] = "BAPED";
        bogle.cBogle[2] = "CTANK";
        bogle.cBogle[3] = "DOOOO";
        bogle.cBogle[4] = "AGBCC";*/
 
 
        std::cin >> nWordNum;
        getchar();
        //nWord.clear();
        /*Word::bundle nBundle;

        nBundle.sWord="EAT";
        nBundle.sHasWord = "NO";
        bogle.cWord.cWordVec.push_back(nBundle);

        nBundle.sWord = "APPLE";
        nBundle.sHasWord = "NO";
        bogle.cWord.cWordVec.push_back(nBundle);

        nBundle.sWord = "PPAP";
        nBundle.sHasWord = "NO";
        bogle.cWord.cWordVec.push_back(nBundle);

        nBundle.sWord = "TANK";
        nBundle.sHasWord = "NO";
        bogle.cWord.cWordVec.push_back(nBundle);*/
 
 
        for (int j = 0; j < nWordNum; ++j)
        {
            
            Word::bundle nBundle;
            std::getline(std::cin, nBundle.sWord);
            nBundle.sHasWord = "NO";
            bogle.cWord.cWordVec.push_back(nBundle);
            
        }
        nBogleList.push_back(bogle);
 
    }
    //std::cout << sizeof(std::string*) << std::endl;
 
    for(std::vector<Bogle>::iterator iter = nBogleList.begin(); iter != nBogleList.end(); iter++)
    {
        iter->CheckWord();
    }
 
    for (std::vector<Bogle>::iterator iter = nBogleList.begin(); iter != nBogleList.end(); iter++)
    {
        for (auto word : iter->cWord.cWordVec)
        {
            std::cout << word.sWord << " " << word.sHasWord << std::endl;
        }
    }
 
 
 
 
    return 0;
}
 
void Bogle::CheckWord()
{
    for (auto& bundle : cWord.cWordVec)
    {
        
        for (int i=0; i < 5;  ++i)
        {
            for (int j=0; j < 5; ++j)
            {
                if (HasWord(i, j, bundle.sWord))
                {
                    bundle.sHasWord = "YES";
                    i = 100;
                    break;
                }
            }
        }
        
    }
    
 
 
}
 
bool Bogle::HasWord(int x, int y, const std::string& word)
{
    //기저사례 시작위치가 범위 밖이면 무조건 실패
    if(!inRange(x, y)) return false;
    //기저사례2 첫 글자까 일치하지 않으면 실패
    if (cBogle[x][y] != word[0]) return false;
    //기저사례3 단어 길이가 1이면 성공
    if (word.size() == 1) return true;
    //인접한 여덟칸을 검사한다.
    for (int direction = 0; direction < 8; ++direction)
    {
        int nextX = x + dx[direction];
        int nextY = y + dy[direction];
 
        if (HasWord(nextX, nextY, word.substr(1)))
            return true;
    }
    return false;
 
 
}
 
bool Bogle::inRange(int x, int y)
{
    if (x < 0 || x > 4)
        return false;
    if (y < 0 || y > 4)
        return false;
    return true;
 
}