BOGGLE 문제 질문입니다(메모이제이션 활용 예제/시간초과 문제 맞음)

  • leithianz
    leithianz
    #include <cstdio>
    #include <cstring>
    #include <iostream>
    #include <algorithm>
    using namespace std;
    
    const int dx[] = {-1, -1, -1, 0, 0, 1, 1, 1};
    const int dy[] = {-1, 0, 1, -1, 1, -1, 0, 1};
    bool memoization[5][5][11];
    char board[5][6];
    
    bool hasWord(int x, int y, int count, const string& word);
    bool inRange(int x, int y);
    
    int main()
    {
        int t, w_num;
        char tmp[11];
        scanf("%d", &t);
        for (int test = 0; test < t; test++) {
            for (int i = 0; i < 5; i++)
                scanf("%s", board[i]);
            scanf("%d", &w_num);
            for (int w = 0; w < w_num; w++) {
                scanf("%s", tmp);
                string word = tmp;
                memset(memoization, true, sizeof(memoization));
                bool found = false;
                for (int r = 0; r < 5; r++) {
                    for (int c = 0; c < 5; c++) {
                        if (hasWord(r, c, 0, word)) {
                            found = true;
                            break;
                        }
                    }
                    if (found)
                        break;
                }
                if (found)
                    printf("%s YES\n", tmp);
                else
                    printf("%s NO\n", tmp);
            }
        }
    }
    
    bool hasWord(int x, int y, int count, const string& word)
    {
        bool ret;
        if (!inRange(x, y))
            return false;
        if (!memoization[x][y][count])
            return false;
        if (word[count] != board[x][y]) {
            // memoization[x][y][count] = false;
            return false;
        }
        if (count+1 == word.length())
            return true;
        for (int dir = 0; dir < 8; dir++) {
            int nx = x + dx[dir], ny = y + dy[dir];
            if (hasWord(nx, ny, count+1, word))
                ret = true;
        }
        if (!ret) {
            memoization[x][y][count] = false;
            return false;
        }
        return true;
    }
    
    bool inRange(int x, int y)
    {
        if (x < 0 || x >= 5 || y < 0 || y >= 5)
            return false;
        else
            return true;
    }
    

    BOGGLE
    위가 해당 코드이고, 종만북 6장의 코드에 메모이제이션만 조금 더해서 풀었습니다.
    예제는 물론이고 시간초과 문제들도 맞다고 나오는데 3500ms 부근에서 오답처리가 납니다.
    혹시나 싶어 테스트 케이스가 여러개인 경우(보글판 자체를 여러번 받아오는 경우)도 테스트 해보았지만 정상적으로 출력이 되었습니다.
    어느 부분이 문제인지 도와주실 수 있으시다면 정말 감사하겠습니다ㅠㅠ


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