BOJ 9202번 Boggle

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

github : https://github.com/junho0956/Algorithm/blob/master/9202/9202/%EC%86%8C%EC%8A%A4.cpp

 

2가지 방법으로 해결했습니다.

trie 자료구조 복습겸 작성해봤고, trie 없이 dfs 하는 방식으로 해봤습니다.

 

trie 자료구조를 이용한 방법

//Boggle
 //일반적인 DFS 문제인데 현재 탐색을 기준 문자열이 존재하는지 없는지 확인하는 작업이 필요하다
 //DFS의 탐색때 마다 모든 문자열을 확인 작업하게되면 TLE가 될 것이다
 //문자열을 빠르게 찾기 위해서는 수업시간에 배운 trie 자료구조를 사용해야한다.
 //문자트리 라고 생각하면 된다
 
#include <fstream>
#include <iostream>
#include <string>
#include <cstring>
#include <set>
using namespace std;
 
ifstream fcin("large_hand.in");
ofstream fcout("large_hand.out");
 
int w, b;
int visit[4][4];
string board[4];
set<string> key;
int score[9] = { 0,0,0,1,1,2,3,5,11 };
int my[8] = { -1,-1,-1,0,0,1,1,1 };
int mx[8] = { -1,0,1,-1,1,-1,0,1 };
 
struct trie {
    // 알파벳A~Z까지에 대한 배열
    trie* node[26];
    // 단어의 종료를 알리는 배열
    bool finish;
 
    // new 를 위한 생성자
    trie() {
        memset(this->node, NULL, sizeof(this->node));
        this->finish = false;
    }
 
    // 스트링에 대한 트라이트리 만들기
    // 현재 포인터에 대한 다음 포인터가 없다면 연결을 위해 만들어준다
    void insert(string s) {
        trie* p = this;
        for (int i = 0; i < s.length(); i++) {
            int index = s[i] - 'A';
            if (p->node[index] == NULL)
                p->node[index] = new trie();
            p = p->node[index];
        }
        // 단어의 종료를 알려줘야한다
        p->finish = true;
    }
 
    void search(int y, int x, string s) {
        // 단어가 8글자이하라고 했다
        if (s.length() > 8) return;
 
        visit[y][x] = 1;
        s += board[y][x];
 
        trie* check = this->node[board[y][x] - 'A'];
        // 현재 포인터에 대해 방금 추가한 단어가 없다 -> 연결안되있다면 반환
        if (check == NULL) {
            visit[y][x] = 0;
            return;
        }
 
        // 중복처리를 위해 set 처리
        if (check->finish) key.insert(s);
 
        for (int i = 0; i < 8; i++) {
            int yy = y + my[i];
            int xx = x + mx[i];
            if (yy >= 0 && yy < 4 && xx >= 0 && xx < 4 && visit[yy][xx] == 0) {
                check->search(yy, xx, s);
            }
        }
        // dfs 에 의한 방문처리
        visit[y][x] = 0;
    }
};
 
int main() {
    ios::sync_with_stdio(0), fcin.tie(0), fcout.tie(0);
 
    // trie의 루트노드
    trie* root = new trie();
 
    fcin >> w;
    while (w--) {
        string str;
        fcin >> str;
        // 단어추가
        root->insert(str);
    }
 
    fcin >> b;
    while (b--) {
        key.clear();
        for (int i = 0; i < 4; i++)
            fcin >> board[i];
 
        // 0.0 부터 3.3 까지 전부 탐색해준다
        for (int i = 0; i < 4; i++)
            for (int j = 0; j < 4; j++)
                root->search(i, j, "");
 
        string longstr = "";
        int total = 0, findNum = key.size();
        for (string po : key) {
            total += score[po.length()];
 
            if (longstr.length() == po.length())
                longstr = longstr < po ? longstr : po;
            else if (longstr.length() < po.length())
                longstr = po;
        }
 
        fcout << total << " " << longstr << " " << findNum << "\n";
    }
    return 0;
}

 

trie 없이 기본 dfs 로만 구현

#include <iostream>
#include <set>
#include <vector>
#include <string>
#include <algorithm>
using namespace std;
 
int w, b;
string board[4];
bool visit[4][4], isFind;
string isWant;
set<string> key;
int score[9] = { 0,0,0,1,1,2,3,5,11 };
int my[8] = { -1,-1,-1,0,0,1,1,1 };
int mx[8] = { -1,0,1,-1,1,-1,0,1 };
string v[300001];
 
void search(int y, int x, int index) {
    if (isFind || index >= isWant.size()) return;
    if (isWant[index] != board[y][x]) return;
 
    visit[y][x] = true;
 
    if (index == isWant.size() - 1 && board[y][x] == isWant[index]) {
        key.insert(isWant);
        isFind = true;
        visit[y][x] = false;
        return;
    }
 
    for (int i = 0; i < 8; i++) {
        int yy = y + my[i];
        int xx = x + mx[i];
        if (yy >= 0 && yy < 4 && xx >= 0 && xx < 4 && visit[yy][xx] == 0) {
            search(yy, xx, index + 1);
            if (isFind) {
                visit[y][x] = false;
                return;
            }
        }
    }
 
    visit[y][x] = false;
}
 
int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);
 
    cin >> w;
    for (int i = 0; i < w; i++) cin >> v[i];
 
    cin >> b;
    while (b--) {
        key.clear();
        for (int i = 0; i < 4; i++)
            cin >> board[i];
        for (int k = 0; k < w; k++) {
            bool t = false;
            for (int i = 0; i < 4; i++) {
                for (int j = 0; j < 4; j++) {
                    if (board[i][j] == v[k][0]) {
                        isFind = false;
                        isWant = v[k];
                        int num = key.size();
                        search(i, j, 0);
                        if (num != key.size()) { t = true; break; }
                    }
                }
                if (t) break;
            }
        }
        string longest = "";
        int total = 0, cnt = key.size();
        for (string at : key) {
            if (longest.length() == at.length())
                longest = longest < at ? longest : at;
            else if (longest.length() < at.length())
                longest = at;
            total += score[at.length()];
        }
        cout << total << " " << longest << " " << cnt << "\n";
    }
}