보글게임(BOGGLE) 문제 시간초과!

  • EggCracker
    EggCracker

    안녕하세요?

    알고리즘 문제해결전략 책을 구매하고

    6장에 나와있는 예제인 보글게임을 풀고있습니다.

    교재와 동일한 알고리즘으로 구현하였는데 계속해서 시간초과가 뜨네요.

    실수한 부분이 있을수도 있지만 제 눈엔 안띄네요 ㅜㅜ
    소스코드 첨부합니다..

    #include <iostream>
using namespace std;

const int dx[8] = {-1, -1, -1, 1, 1, 1, 0, 0};
const int dy[8] = {-1, 0, 1, -1, 0, 1, -1, 1};

char board[5][6];

bool inRange(int y, int x)
{
    if( y < 0 || y > 4 || x < 0 || x > 4)
        return false;
    return true;
}

bool hasWord(int y, int x, const string& word)
{
    if(!inRange(y, x))
        return false;

    if(board[y][x] != word[0])
        return false;

    if(word.size() == 1)
        return true;

    for(int direction=0; direction<8; direction++)
    {
        int nextY = y + dy[direction];
        int nextX = x + dx[direction];

        if(hasWord(nextY, nextX, word.substr(1)))
            return true;
    }
    return false;
}

int main()
{
    int testCase;
    cin >> testCase;

    while( testCase-- )
    {
        for(int i=0; i<5; i++)
            cin >> board[i];
        int n;
        cin >> n;

        for(int i=0; i<n; i++)
        {
            char word[11];
            cin >> word;

            bool isOK = false;
            for(int j=0; j<5; j++)
            {
                for(int k=0; k<5; k++)
                    if( hasWord(j, k, word) )
                    {
                        isOK = true;
                        break;
                    }
                if( isOK )
                    break;
            }
            if( isOK )
                cout << word << " YES";
            else
                cout << word << " NO";
            cout << endl;
        }
    }
}

    11년 전
8개의 댓글이 있습니다.
  • EggCracker
    EggCracker

    왠지 메인함수에서 무한루프를 도는 것 같은데 일단 찾아보고 다시들를게요ㅎㅎ


    11년 전 link
  • ejn
    ejn

    그 다음 페이지에 설명이 나와 있더군요.. 자세히 읽어보시면 아마 이유를 아시게 될 듯..


    11년 전 link
  • EggCracker
    EggCracker

    감사합니다. 이부분때문에 두시간 가까이 고민했는데, 6장에서 이야기하는 방법으론 해결할 수 없는 문제였나보네요.


    11년 전 link
  • JongMan
    JongMan

    제가 본의 아니게 이런 낚시를 했군요. -_-; 해당 문제에 경고문을 달아두어야겠습니다. ㅜㅜ


    11년 전 link
  • JongMan
    JongMan

    고생시켜드려서 죄송해요~ 흑흑..


    11년 전 link
  • JongMan
    JongMan

    BOGGLE 추가했습니다.


    11년 전 link
  • EggCracker
    EggCracker

    감사드려요ㅎㅎ


    11년 전 link
  • sst
    sst

    저도 왜 안풀리나 고민좀 했는데 ㅋㅋㅋㅋㅋ 속시원하네요


    11년 전 link

  • 정회원 권한이 있어야 커멘트를 다실 수 있습니다. 정회원이 되시려면 온라인 저지에서 5문제 이상을 푸시고, 가입 후 7일 이상이 지나셔야 합니다. 현재 문제를 푸셨습니다.