BOGGLE (중하, p. 150)

책에서는 난이도 ‘하’로 소개되는데, 150페이지 책 풀이인 완탐으로 하게 되면 AC를 받을 수 없고, DP로 풀어야 한다. 그래서 난이도를 ‘중하’로 지정했다.

최대 10개 단어가 주어지고, 각 단어는 최대 10글자이며, 5x5 board에서 지나갔던 곳을 다시 지나갈 수 있으므로 $10\times8^{9}$만큼의 시간이 필요하다. (왜냐하면, 8개의 방향으로 10글자의 단어를 만드는 방법의 수가 $8^{10-1}$이고, 이러한 단어가 최대 10개 있기 때문에 10을 곱했다.) 즉, 완탐으로 하면 $O(12.8억)$이므로 26초 정도의 시간이 필요하다. → RTE!!

풀이법은 (x,y)로 끝나는 문자열을 hash table에 저장하는 것이다. (DP)

물론 모든 경우를 다 저장할 수는 없고, 주어진 10개의 단어를 포함하는 경우만 저장하면 된다.

#include <cstdio>
#include <cstring>
#include <iostream>
#include <string>
#include <unordered_map>
#include <vector>
#include <set>

using namespace std;
string board[5];
int dx[] = {-1, -1, -1, 0, 1, 1, 1, 0};
int dy[] = {-1, 0, 1, 1, 1, 0, -1, -1};

struct Coord {
    int x, y;
    Coord() {}
    Coord(int x, int y) : x(x), y(y) {}
    bool operator<(const Coord& rhs) const {
        if (x == rhs.x)
            return y < rhs.y;
        else
            return x < rhs.x;
    }
};

unordered_map<string, Coord> udic;
string s[11];
set<string> str_set[11][5][5];

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    int tc;
    cin >> tc;

    for (int i = 0; i < 5; i++) {
        for (int j = 0; j < 5; j++) {
            str_set[0][i][j].clear();
            str_set[0][i][j].insert("");
        }
    }

    while (tc--) {
        //init
        for(int len=1; len<=10; len++) {
            for(int i=0; i<5; i++) {
                for(int j=0; j<5; j++) {
                    str_set[len][i][j].clear();
                }
            }
        }
        udic.clear();

        //input
        for (int i = 0; i < 5; i++) {
            cin >> board[i];
        }

        int N;
        cin >> N;
        for (int i = 0; i < N; i++) {
            cin >> s[i];
        }

        string sub_str;
        for (int len = 1; len <= 10; len++) {
            for (int i = 0; i < 5; i++) {
                for (int j = 0; j < 5; j++) {
                    for (int a = 0; a < N; a++) {
                        if (s[a].size() < len) continue;
                        if (s[a][len-1] != board[i][j]) continue;
                        sub_str.clear();
                        if(len>1) sub_str = s[a].substr(0,len-1);

                        for (int k = 0; k < 8; k++) {
                            int pi = i + dx[k];
                            int pj = j + dy[k];
                            if (pi < 0 || pj < 0 || pi >= 5 || pj >= 5) continue;
                            if(str_set[len-1][pi][pj].count(sub_str)) {
                                str_set[len][i][j].insert(sub_str+string(1,board[i][j]));
                                udic[sub_str+string(1,board[i][j])] = Coord(i,j);
                            }
                        }
                    }
                }
            }
        }

        for (int i = 0; i < N; i++) {
            printf("%s ", s[i].c_str());
            if (udic.count(s[i]))
                puts("YES");
            else
                puts("NO");
        }
    }
    return 0;
}

코드가 좀 구데기 같은데.. 나중에 손봐보자. 재귀로 푸는게 더 깔끔할 것 같다.