[BOJ] 9202 : Boggle

문제 : www.acmicpc.net/problem/9202

---

Sort Backtracking BinarySearch

[ 알고리즘풀이 ]

 

-Sorting

1) 단어사전을 입력받고 sort를 진행한다. ( binary search 를 위해 )

 

-Backtracking

2) 4 x 4 보드 판을 입력받고, 모든 지점에서 만들 수 있는 모든 단어를 Backtracking 을 이용해서 만든다.

 

-BinarySearch 

3) 만들어진 단어가 단어사전에 있는지 binary search를 이용해 탐색한다.

 

4) 이진탐색 결과가 실패라면 넘어가고, 성공이라면 가장 긴 단어와 score, 단어 count를 갱신한다.

이때, 같은 단어를 만들어서 찾은 경우라면 한 번만 count 해야 되므로 isSelected bool 배열을 이용해 단어 사전에서 탐색에 성공한 단어들은 체크해둔다.

 

 5) (2) ~ (4) 과정을 보드판마다 반복한다.

 

[ 코드구현 C++ ]

#include<iostream>
#include<vector>
#include<string>
#include<algorithm>
#include<cstring>
 
using namespace std;
 
int w, b;
int scores[9] = { 0, 0, 0, 1, 1, 2, 3, 5, 11 };
int dx[8] = { -1, -1, -1, 0, 1, 1, 1, 0 }, dy[8] = { -1, 0, 1, 1, 1, 0, -1, -1 };
 
string dictionary[300000];
 
int cnt, score;
bool isSelected[300000];
bool visited[4][4];
string board[4];
string longWord;
 
bool isInside(int x, int y) {
    return (0 <= x && x < 4 && 0 <= y && y < 4);
}
 
int binary_search(string word) {
    int left = 0, right = w - 1;
    while (left <= right) {
        int mid = (left + right) / 2;
        if (dictionary[mid] == word) return mid;
        else if (dictionary[mid] < word) left = mid + 1;
        else right = mid - 1;
    }
    return -1;
}
 
void makeWord(int x, int y, string word) {
    if (int(word.length()) >= 9) return;
    if (word.length() >= 1) {
        // binarySearch로 찾기
        int ind = binary_search(word);
        if (ind != -1) {
            if (word.length() > longWord.length()) longWord = word;
            else if (word.length() == longWord.length() && word < longWord) longWord = word;
            if (!isSelected[ind]) {
                isSelected[ind] = 1;
                cnt++;
                score += scores[word.length()];
            }
        }
    }
 
    for (int i = 0; i < 8; i++) {
        int nextX = x + dx[i], nextY = y + dy[i];
        if (!isInside(nextX, nextY)) continue;
        if (visited[nextX][nextY]) continue;
 
        visited[nextX][nextY] = 1;
        word.push_back(board[nextX][nextY]);
        makeWord(nextX, nextY, word);
        word.pop_back();
        visited[nextX][nextY] = 0;
    }
}
int main(void) {
    ios::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
 
    cin >> w;
    for (int i = 0; i < w; i++)
        cin >> dictionary[i];
 
    sort(dictionary, dictionary + w);
 
    cin >> b;
    for (int i = 0; i < b; i++) {
        for (int j = 0; j < 4; j++)
            cin >> board[j];
 
        memset(isSelected, 0, sizeof(isSelected));
        longWord = "";
        cnt = 0;
        score = 0;
 
        string word;
        for (int j = 0; j < 4; j++)
            for (int k = 0; k < 4; k++){
                word.push_back(board[j][k]);
                visited[j][k] = 1;
                makeWord(j, k, word);
                visited[j][k] = 0;
                word.pop_back();
            }
        cout << score << ' ' << longWord << ' ' << cnt << '\n';
    }
}

[ github ]

github.com/travelbeeee/ProblemSolving/blob/master/BOJ/BOJ9202.cpp

travelbeeee/ProblemSolving

---