티스토리 뷰

알고리즘 관련/BOJ

BOJ)9202 Boggle

JASON 자손9319 2017. 2. 4. 04:30

문제: icpc.me/9202


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


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


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


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


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
#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,};
int dy[] = { -1,1,-1,0,1,-1,0,};
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, 0sizeof(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 < || j < || i >= || 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;
}
cs


'알고리즘 관련 > BOJ' 카테고리의 다른 글

BOJ)14431 소수마을  (0) 2017.02.06
BOJ) 10282 Failing Components  (0) 2017.02.04
BOJ)9202 Boggle  (0) 2017.02.04
BOJ)5052 전화번호 목록  (0) 2017.02.03
BOJ)2662 기업투자  (0) 2017.02.03
BOJ)9252 LCS 2  (0) 2017.02.02
댓글
댓글쓰기 폼