BOJ)9202 Boggle

문제: icpc.me/9202

점수를 얻을 수 있는 문자열 셋이 주어진 뒤 Boggle 보드가 주어질 때 주어진 Boggle 보드에서 얻을 수 있는 최고점수 가장 긴 문자열 찾은 단어의 수를 출력하는 문제이다.

단어 사전에 단어가 30만개 까지 들어올 수 있으므로 트라이를 이용하여 해결하면 쿼리를 매번 최대 단어의 길이안에 처리해줄 수 있다.

우리는 단어 사전의 모든 단어들을 Trie에 저장해 준 후 

Boggle 보드에서 Bruteforce를 통하여 모든 경우를 탐색하여 나올 수 있는 문자열들을 set에 저장해 준 뒤 답을 출력해주면 된다.

#include <cstdio>
#include <algorithm>
#include <string>
#include <set>
#include <cstring>
#include <vector>
#include <iostream>
using namespace std;
int dx[] = { 0,0,-1,-1,-1,1,1,1 };
int dy[] = { -1,1,-1,0,1,-1,0,1 };
int score[] = { 0,0,0,1,1,2,3,5,11 };
set<string> res;
bool visited[4][4];
string boggle[4];
int w, b;
struct Trie {
    bool finish;
    Trie* next[26];
    Trie() : finish(false) {
        memset(next, 0, sizeof(next));
    }
    ~Trie() {
        for (int i = 0; i < 26; i++)
            if (next[i])
                delete next[i];
    }
    void insert(const char* key) {
        if (*key == '\0')
            finish = true;
        else {
            int curr = *key - 'A';
            if (next[curr] == NULL)
                next[curr] = new Trie();
            next[curr]->insert(key + 1);
        }
    }
    void query(int i, int j, string cur) {
        if (i < 0 || j < 0 || i >= 4 || j >= 4)return;
        if (visited[i][j])return;
        if (cur.size() >= 8)return;
 
        visited[i][j] = true;
        cur = cur + boggle[i][j];
        if (next[boggle[i][j] - 'A'] == '\0') {
            visited[i][j] = false;
            return;
        }
        if (next[boggle[i][j] - 'A']->finish)
            res.insert(cur);
        for (int c = 0; c < 8; c++) {
            next[boggle[i][j] - 'A']->query(i + dx[c], j + dy[c], cur);
        }
        visited[i][j] = false;
    }
};
int main() {
    scanf("%d", &w);
    Trie *root = new Trie;
    getchar();
    for (int i = 0; i < w; i++) {
        char t[10];
        scanf("%s", &t);
        root->insert(t);
    }
    scanf("%d", &b);
    for (int i = 0; i < b; i++) {
        for (int j = 0; j < 4; j++)cin >> boggle[j];
        res.clear();
        for (int j = 0; j < 4; j++) {
            for (int k = 0; k < 4; k++) {
                root->query(j, k, "");
            }
        }
        string longstr = *(res.begin());
        int tscore = 0;
        for (auto it : res) {
            if (longstr.size() < it.size())
                longstr = it;
            tscore += score[it.size()];
        }
        cout << tscore << " " << longstr << " " << res.size() << "\n";
    }
    return 0;
}