[C++][백준 9202] Boggle

문제

접근 방법

트라이, 백트래킹으로 생각했다.
트라이를 활용하면 모든 문자열을 확인할 필요 없이 트리를 따라가면 되고 만약 트리에 존재하지 않는다면 무시하면 되기 때문이다.

트라이에서 문자열의 끝이라고 지정해 둔 부분에 방문한다면 중복되지 않았는지, 가장 길고 사전 순으로 앞서는지 확인해서 갱신하면 된다고 생각했다.

코드

#include <iostream>
#include <unordered_map>
#include <unordered_set>
#include <string>
#include <cstring>
using namespace std;
struct trie
{
    unordered_map<char, trie *> um;
    bool isEnd;
};
trie *root;
int w, b, maxScore;
unordered_set<string> isUsed;
string temp, ret;
char grid[4][4];
bool isVisited[4][4];
int dy[] = {0, 0, 1, -1, 1, -1, 1, -1}, dx[] = {1, -1, 0, 0, 1, -1, -1, 1}, score[] = {0, 0, 1, 1, 2, 3, 5, 11};
void dfs(int y, int x, trie *cur)
{
    if (cur->isEnd)
        if (isUsed.find(temp) == isUsed.end())
        {
            isUsed.insert(temp);
            maxScore += score[temp.length() - 1];
            if (ret.length() < temp.length())
                ret = temp;
            else if (ret.length() == temp.length() && ret > temp)
                ret = temp;
        }
    for (int i = 0; i < 8; ++i)
    {
        int ny = y + dy[i], nx = x + dx[i];
        if (ny < 0 || nx < 0 || ny >= 4 || nx >= 4 || isVisited[ny][nx])
            continue;
        char c = grid[ny][nx];
        if (cur->um.find(c) == cur->um.end())
            continue;
        isVisited[ny][nx] = true;
        temp.push_back(c);
        dfs(ny, nx, cur->um[c]);
        temp.pop_back();
        isVisited[ny][nx] = false;
    }
}
int main()
{
    ios::sync_with_stdio(0), cin.tie(0);
    root = new trie();
    cin >> w;
    for (int i = 0; i < w; ++i)
    {
        trie *cur = root;
        cin >> temp;
        for (char c : temp)
        {
            if (cur->um.find(c) == cur->um.end())
                cur->um[c] = new trie();
            cur = cur->um[c];
        }
        cur->isEnd = true;
    }
    cin >> b;
    while (b--)
    {
        isUsed.clear();
        memset(isVisited, false, sizeof(isVisited));
        ret = "";
        maxScore = 0;
        for (int i = 0; i < 4; ++i)
        {
            cin >> temp;
            for (int j = 0; j < 4; ++j)
                grid[i][j] = temp[j];
        }
        for (int i = 0; i < 4; ++i)
        {
            for (int j = 0; j < 4; ++j)
            {
                char c = grid[i][j];
                if (root->um.find(c) == root->um.end())
                    continue;
                isVisited[i][j] = true;
                temp = c;
                dfs(i, j, root->um[c]);
                isVisited[i][j] = false;
            }
        }
        cout << maxScore << " " << ret << " " << isUsed.size() << "\n";
    }
    return 0;
}

풀이

크기는 30개의 보드에 4x4 그리드이다.
대략 생각해 보면 4x4 그리드를 각 위치에서 모두 탐색한다고 하면 4^4일 것이다.
거기에 30을 곱하면 4^4*30인 것이다.
무엇보다 시간제한이 10초다.
완전 탐색을 해도 된다고 생각한다.

탐색 과정에서 조건이 부합하는지 확인하는 과정을 줄여야 하는 것이다.
트라이를 활용하여 문자열에 중복된 부분들을 단축해 는 것 같다.