[백준 9202] boggle (C++)

https://www.acmicpc.net/problem/9202

 

- 문제 설명

 

Boggle이라는 보드 게임이 있습니다. 글자가 쓰여 있는 주사위로 이루어진 4x4 크기의 그리드에서 최대한 많은 단어를 찾는 게임입니다. 글자수 마다 점수가 주어져있습니다. 단어 사전에 등재되어 있는 단어의 목록과 Boggle 게임 보드가 주어졌을 때, 얻을 수 있는 최대 점수, 가장 긴 단어, 찾은 단어의 수를 구하는 프로그램을 작성하는 것이 목표입니다.

 

- 입력

 

첫째 줄에 단어 사전에 들어있는 단어의 수 w가 주어진다. (1 < w < 300,000) 다음 w개 줄에는 단어가 주어진다. 단어는 최대 8글자이고, 알파벳 대문자로만 이루어져 있다. 단어 사전에 대한 정보가 모두 주어진 이후에는 빈 줄이 하나 주어진다.

 

그 다음에는 Boggle 보드의 개수 b가 주어진다. (1 < b < 30) 모든 Boggle은 알파벳 대문자로 이루어져 있고, 4줄에 걸쳐 주어진다. 각 Boggle의 사이에는 빈 줄이 하나  있다.

 

- 출력

 

각각의 Boggle에 대해, 얻을 수 있는 최대 점수, 가장 긴 단어, 찾은 단어의 개수를 출력한다. 한 Boggle에서 같은 단어를 여러 번 찾은 경우에는 한 번만 찾은 것으로 센다. 가장 긴 단어가 여러 개인 경우에는 사전 순으로 앞서는 것을 출력한다. 각 Boggle에 대해서 찾을 수 있는 단어가 적어도 한 개인 경우만 입력으로 주어진다.

 

- 풀이

 

단어 사전이 주어지면 해당 단어들을 트라이로 만들어 저장하고, Boggle을 dfs로 만들어 질 수 있는 모든 단어들을 트라이에서 검색하여 찾습니다. 트라이에서 해당 단어를 찾을 때 조금 생각해야 하는 부분이 있습니다. 

예를 들어, Boggle에서 현재 찾은 단어가 AB이고, Trie에 ABC가 저장되어 있다고 가정한다면 현재 찾은 단어는 유망한 단어, 즉 앞으로 C가 더 나온다면 단어 사전에 등재된 단어를 찾는 것이기 때문에 dfs탐색을 멈추지 않고 더 깊이 탐색하게 됩니다. 

또 생각해 볼 문제가 있는데, "Boggle에 대해서 찾을 수 있는 단어가 적어도 한 개인 경우만 입력으로 주어진다."라고 했기 때문에 찾은 단어들은 겹치면 안된다는 문제가 있습니다. 겹치면 안된다는 것에서 바로 Set자료 구조를 떠올릴 수 있지만, 저는 Trie의 특성 중에서 terminal이 true이면 해당 노드에 적절한 표시를 통해 이미 찾은 단어임을 알 수 있다는 것을 이용하였습니다.

 

- 코드

 

#include <iostream>
#include <algorithm>
#include <vector>
#define endl "\n"
 
int w, b;
int cnt, score;
std::string longest_word;
 
std::vector<std::string> dice;
std::vector<bool> visited;
std::vector<std::pair<int, int> >dir;
struct trie;
trie *p;
bool not_count;
 
int to_number(char ch)
{
    return (ch - 'A');
}
 
void score_board(std::string &word)
{
    if (word.size() == 3 || word.size() == 4)
        score += 1;
    else if (word.size() == 5)
        score += 2;
    else if (word.size() == 6)
        score += 3;
    else if (word.size() == 7)
        score += 5;
    else if (word.size() == 8)
        score += 11;
}
struct trie
{
    std::vector<trie *>children;
    std::vector<bool> t_visited;
    bool terminal;
    trie(): terminal(false)
    {
        children.resize(26, nullptr);
        t_visited.resize(30, 0);
    }
    ~trie()
    {
        for(size_t i = 0 ; i < 26; i++)
            if(children[i])
                delete children[i];
    }
 
    void insert(std::string &key, int i)
    {
        if (key[i] == '\0')
            terminal = true;
        else
        {
            int next = to_number(key[i]);
            if (children[next] == nullptr)
                children[next] = new trie();
            children[next]->insert(key, i + 1);
        }
    }
 
    trie* find(std::string &key, int i, int &boggle)
    {
        if (key[i] == '\0')
        {
            if ((t_visited[boggle] && terminal) || !terminal)
                not_count = 1;
            else if (terminal)
                t_visited[boggle] = true;
            return (this);
        }
        int next = to_number(key[i]);
        if (children[next] == nullptr)
            return (nullptr);
        return (children[next]->find(key, i+1, boggle));
    }
};
 
void input_faster()
{
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(0);
    std::cout.tie(0);
}
 
void input()
{
    int i = -1;
 
    input_faster();
    std::cin >> w;
    p = new trie();
    while(++i < w)
    {
        std::string tmp;
        std::cin >> tmp;
        p->insert(tmp, 0);
    }
    std::cin >> b;
    dir = {{0, 1}, {1, 1}, {1, 0}, {1, -1}, {0, -1}, {-1, -1}, {-1, 0}, {-1, 1}};
}
 
void dfs(int i, int j, std::string word, int &boggle)
{
    if (i < 0 || j < 0 || i >= 4 || j >= 4 || visited[i*4 + j] || word.size() > 8)
        return ;
    word.push_back(dice[i][j]);
    not_count = 0;
    if (p->find(word, 0, boggle) == nullptr)
        return;
    visited[i*4 + j] = 1;
    if (!not_count)
    {
        if(word.size() > longest_word.size())
        {
            longest_word = "";
            longest_word = word;
        }
        else if (word.size() == longest_word.size())
        {
 
            if(word.compare(longest_word) < 0)
            {
                longest_word = "";
                longest_word = word;
 
            }
        }
        cnt++;
        score_board(word);
    }
    for (size_t x = 0 ; x < 8 ; x++)
        dfs (i + dir[x].first, j + dir[x].second, word, boggle);
    visited[i*4 + j] = 0;
}
 
void solve()
{
    int i;
    std::string word;
 
    score = 0;
    cnt = 0;
    i = -1;
    dice = std::vector<std::string>(4);
    while (++i < 4)
    {
        dice[i].resize(4);
        std::cin >> dice[i];
    }
    word = "";
    longest_word = "";
    for(int i = 0 ; i < 4 ; i++)
        for(int j = 0 ; j < 4 ; j++)
        {
            visited = std::vector<bool> (16,0);
            dfs(i, j , word, b);
        }
    std::cout << score << " " << longest_word << " " << cnt << endl;
}
 
int main()
{
    input();
    while(b--)
        solve();
    delete (p);
    return (0);
}