[BOJ/Platinum 5] 백준 9202 Boggle(C++)

문제 링크

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

9202번: Boggle

 

문제

상근이는 보드 게임 "Boggle"을 엄청나게 좋아한다. Boggle은 글자가 쓰여 있는 주사위로 이루어진 4×4 크기의 그리드에서 최대한 많은 단어를 찾는 게임이다. 

상근이는 한 번도 부인을 Boggle로 이겨본 적이 없다. 이렇게 질 때마다 상근이는 쓰레기 버리기, 설거지와 같은 일을 해야 한다. 이제 상근이는 프로그램을 작성해서 부인을 이겨보려고 한다.

Boggle에서 단어는 인접한 글자(가로, 세로, 대각선)를 이용해서 만들 수 있다. 하지만, 한 주사위는 단어에 한 번만 사용할 수 있다. 단어는 게임 사전에 등재되어 있는 단어만 올바른 단어이다.

1글자, 2글자로 이루어진 단어는 0점, 3글자, 4글자는 1점, 5글자는 2점, 6글자는 3점, 7글자는 5점, 8글자는 11점이다. 점수는 자신이 찾은 단어에 해당하는 점수의 총 합이다.

단어 사전에 등재되어 있는 단어의 목록과 Boggle 게임 보드가 주어졌을 때, 얻을 수 있는 최대 점수, 가장 긴 단어, 찾은 단어의 수를 구하는 프로그램을 작성하시오.

입력

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

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

출력

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

예제 입력 1

5
ICPC
ACM
CONTEST
GCPC
PROGRAMM

3
ACMA
APCA
TOGI
NEST

PCMM
RXAI
ORCN
GPCG

ICPC
GCPC
ICPC
GCPC

예제 출력 1

8 CONTEST 4
14 PROGRAMM 4
2 GCPC 2

알고리즘 분류

• 그래프 탐색
• 자료 구조
• 트라이
• 백트래킹

풀이

W개의 단어를 트라이에 insert하고 B번의 보드 게임을 수행한다.

보드의 크기가 4×4이므로, 16번의 DFS를 수행하여 보드에서 찾을 수 있는 모든 단어를 찾는다.

현재 위치한 칸의 알파벳을 가진 현재 노드의 자식 노드가 존재한다면 자식 노드로 이동한다. 그러한 자식 노드가 존재하지 않는다면 해당 노드에서의 탐색을 종료한다.

단어의 길이는 최대 8까지이므로, 이런 식으로 단어를 찾아나가면서 9개 이상의 칸을 탐색했다면 탐색을 종료한다.

단어를 찾았다는 것을 기록해주기 위해서 해싱을 통해 각 단어마다 번호를 매기고, 찾은 단어의 길이에 따라 점수를 증가시킨다.

마지막으로 점수와 길이가 가장 긴 단어, 찾은 단어의 개수를 공백으로 구분하여 출력한다.

코드

#include <iostream>
#include <vector>
#include <string>
#include <map>
#include <algorithm>
#define MAX 300001
#define FASTIO cin.tie(0); cout.tie(0); ios::sync_with_stdio(false);

using namespace std;
struct TRIE {
    bool isEnd;
    TRIE* Child[26];
    TRIE* FailLink;

    TRIE() : isEnd(false), FailLink(nullptr) {
        fill (Child, Child + 26, nullptr);
    }

    ~TRIE() {
        for (int i = 0; i < 26; i++) {
            if (Child[i] != nullptr) {
                delete Child[i];
            }
        }
    }

    void insert_Pattern(string Pattern) {
        TRIE* NowTrie = this;
        for (int i = 0; i < Pattern.size(); i++) {
            int NowAlpha = Pattern[i] - 'A';
            if (NowTrie->Child[NowAlpha] == nullptr) {
                NowTrie->Child[NowAlpha] = new TRIE;
            }
            NowTrie = NowTrie->Child[NowAlpha];
        }
        NowTrie->isEnd = true;
    }
};

int W, B;
string S;
vector<string> Words;
map<string, int> Dict;
bool isFind[MAX];
char MAP[4][4];
bool Visited[4][4];
int MoveY[8] = { -1,-1,-1,0,1,1,1,0 };
int MoveX[8] = { -1,0,1,1,1,0,-1,-1 };
int Score, Count;
string Answer;

void init() {
    for (int i = 0; i < MAX; i++) {
        isFind[i] = false;
    }
    Score = 0;
    Count = 0;
    Answer = "";
}

void init2() {
    for (int i = 0; i < 4; i++) {
        for (int j = 0; j < 4; j++) {
            Visited[i][j] = false;
        }
    }
}

void DFS(int Y, int X, string Str, TRIE* Trie) {
    if (Str.size() > 8) {
        return;
    }

    Visited[Y][X] = true;
    TRIE* NowTrie = Trie;
    int NowA = MAP[Y][X] - 'A';
    if (NowTrie->Child[NowA] != nullptr) {
        NowTrie = NowTrie->Child[NowA];
    }
    else {
        Visited[Y][X] = false;
        return;
    }
    if (NowTrie->isEnd) {
        isFind[Dict[Str]] = true;
    }

    for (int i = 0; i < 8; i++) {
        int NextY = Y + MoveY[i];
        int NextX = X + MoveX[i];
        if ((NextY >= 0) && (NextY < 4) && (NextX >= 0) && (NextX < 4) && !Visited[NextY][NextX]) {
            DFS(NextY, NextX, Str + MAP[NextY][NextX], NowTrie);
        }
    }

    Visited[Y][X] = false;
}

void find_Answer(TRIE* Root) {
    init();
    for (int i = 0; i < 4; i++) {
        for (int j = 0; j < 4; j++) {
            init2();
            string Start = "";
            Start += MAP[i][j];
            DFS(i, j, Start ,Root);
        }
    }
    for (int i = 0; i < W; i++) {
        if (isFind[i]) {
            if ((Words[i].size() >= 3) && (Words[i].size() <= 4)) {
                Score += 1;
            }
            else if (Words[i].size() == 5) {
                Score += 2;
            }
            else if (Words[i].size() == 6) {
                Score += 3;
            }
            else if (Words[i].size() == 7) {
                Score += 5;
            }
            else if (Words[i].size() == 8) {
                Score += 11;
            }
            Count++;
            if (Answer.size() < Words[i].size()) {
                Answer = Words[i];
            }
            else if (Answer.size() == Words[i].size()) {
                Answer = min(Answer, Words[i]);
            }
        }
    }
    cout << Score << " " << Answer << " " << Count << "\n";
}

void input() {
    TRIE* Root = new TRIE();
    cin >> W;
    for (int i = 0; i < W; i++) {
        cin >> S;
        Root->insert_Pattern(S);
        Words.push_back(S);
        Dict.insert(make_pair(S, i));
    }
    cin >> B;
    while (B--) {
        for (int i = 0; i < 4; i++) {
            string Tmp;
            cin >> Tmp;
            for (int j = 0; j < 4; j++) {
                MAP[i][j] = Tmp[j];
            }
        }
        find_Answer(Root);
    };
    delete Root;
}

int main() {
    FASTIO
    input();

    return 0;
}