boggle.png

(출처) https://algospot.com/judge/problem/read/BOGGLE

본 문제는 완전탐색으로 풀려면 대략 25 * (8^n) 개의 경우의 수를 전부 확인해야하고, 그에따라 해당 횟수만큼 반복문을 수행해야한다. (n은 주어진 단어의 길이 - PRETTY, GIRL, REPEAT)

최악의 경우 25 * 10억의 경우의 수를 검색하기때문에 당연히 시간초과가 예상된다. 따라서 메모이제이션을 이용해 중복되는 경우를 지워주기로 했다.

생각한 로직은 5x5 맵에 존재하는 총 25개의 좌표들 각각마다 방문순서에 따른 성공여부를 저장하는 메모이제이션 배열을 생성하는 것이었다.

위 문제 예시로 주어진 그림(a)의 맵과 GIRL라는 단어로 예를 들어보면,

단어 GIRL의 문자열 길이는 4개이기 때문에 그림(a)에서는 총 4번의 움직임이 일어난다. 4번의 움직임으로 'G'-'I'-'R'-'L' 방문순서를 만족하는 경우를 찾으면서 (dp[G][0] = dp[I][1] = dp[R][2] = dp[L][3] = 성공 ) 도중에 일어나는 실패는 저장하여 중복을 피한다.

DP[x좌표,y좌표][방문한 순서] 의 성공여부

=

for (int i = 0; i < 8개의 이동좌표; i++)
{ DP[x(i) 좌표, y(i) 좌표] [방문한 순서 + 1] 의 성공여부 (8개의 경우 중 하나라도 성공하면 성공) }

기저사례 : 주어진 단어의 마지막 문자에 해당하는 방문순서일 때

코드

#define _CRT_SECURE_NO_WARNINGS
#include <vector>
#include <iostream>
#include <string>


using namespace std;



vector<int> dx = { 1,1,1,-1,-1,-1,0,0 };
vector<int> dy = { 0,1,-1,0,1,-1,1,-1 };


int hasWord(vector<vector<int>>& dp, string word, vector<string> &map, int n, int xy)
{
    int obj = 0;
    int x = xy % 5;
    int y = xy / 5;

    int &ret = dp[xy][n];

    if (ret != -1) return ret;

    if (map[y][x] != word[n]) return ret = 0;

    if (n == 0) return ret = 1;

    for (int i = 0; i < dx.size(); i++)
    {
        x += dx[i];
        y += dy[i];

        if (x < 0 | x > 4 | y < 0 | y > 4)
        {
            x -= dx[i];
            y -= dy[i];
            continue;
        }

        xy = x + (y * 5);
        obj = hasWord(dp, word, map, n - 1, xy);
        x -= dx[i];
        y -= dy[i];

        if (obj == 1) break;

    }

    return ret = obj;
}

int main()
{
    int testcase;
    scanf("%d", &testcase);
    getchar();


    for (int j = 0; j < testcase; j++)
    {
        vector<string> map = { "00000","00000", "00000", "00000", "00000" };

        for (int i = 0; i < 5; i++)
        {
            getline(cin, map[i]);
        }

        int wordN;
        scanf("%d", &wordN);
        getchar();
        vector<string> word;

        for (int i = 0; i < wordN; i++)
        {
            string keyword;
            getline(cin, keyword);
            word.push_back(keyword);
        }

        //메인 로직
        for (int i = 0; i < word.size(); i++)
        {
            int obj = -1;
            vector<vector<int>> dp(25, vector<int>(10,-1));

            for (int xy = 0; xy < 25; xy++)
            {
                obj = hasWord(dp, word[i], map, word[i].length() - 1, xy);
                if (obj == 1) break;
            }

            if (obj == 1) cout << word[i] << " YES\n";
            else cout << word[i] << " NO\n";

        }

    }

    return 0;
}