BOJ 9202. Boggle

 

문제 링크

 

문제 풀이

 이 문제는 $4\times 4$ 크기의 그리드에 글자들이 적혀져 있을 때 이 글자들을 이어 만들 수 있는 단어들을 찾는 문제이다. 이때 찾은 단어의 길이에 따라 점수가 주어져 점수가 최대로 되도록 하게 찾기도 해야한다. 주어지는 단어의 개수는 $w \leq 3\times 10^5$이고 단어의 길이는 최대 8이다.

 

 일단 칸의 개수가 16개로 매우 작은 편이기 때문에 DFS로 완전탐색 할 생각을 할 수 있다. 모든 칸에서 최대 $4^8$번 탐색을 하므로 연산 횟수는 $2^{20}$을 넘지 않는다. 그래서 그냥 완전탐색을 하며 중복만 잘 처리해주면 되는 아주 쉬운 문제이다. 참고로 실행시간 절약을 위해 주어진 단어들을 해시 맵 형태로 저장하였다.

 

 

코드

#include <iostream>
#include <algorithm>
#include <string>
#include <vector>
#include <unordered_map>
using namespace std;
int dx[8] = {0,0,1,1,1,-1,-1,-1};
int dy[8] = {1,-1,0,1,-1,0,1,-1};

unordered_map<string,bool> isInDict;
unordered_map<string,bool> isVisited;
vector<string> words;
int w,b,totalWordNum = 0,mxScore = 0;
char BOGGLE[4][4];
string longestWord;
bool visited[4][4];

int transferToScore(int x){
    if(x == 3 || x == 4) return 1;
    if(x == 5) return 2;
    if(x == 6) return 3;
    if(x == 7) return 5;
    if(x== 8) return 11;
    return 0;
}

void input(){
    cin>>w;
    for(int i=0;i<w;i++){
        string s;
        cin>>s;
        isInDict[s] = true;
        words.push_back(s);
    }
    cin>>b;
}

void init(){
    totalWordNum = 0;
    longestWord = "0";
    mxScore = 0;
    for(int i=0;i<w;i++){
        isVisited[words[i]] = false;
    }
}

void DFS(int x, int y, string word, int depth){
    if(isInDict[word] &&!isVisited[word]) {
        isVisited[word] = true;
        int wordLength = word.size();
        mxScore += transferToScore(wordLength);
        totalWordNum ++;
        if(longestWord.size() < wordLength){
            longestWord = word;
        } else if(longestWord.size() == wordLength){
            if(longestWord > word) longestWord = word;
        }
    }
    if(depth == 8) return;
    
    for(int i=0;i<8;i++){
        int nx = x+dx[i];
        int ny = y+dy[i];
        if(nx<0 || nx>=4 || ny<0 || ny>=4) continue;
        if(visited[nx][ny]) continue;
        visited[nx][ny] = true;
        DFS(nx,ny,word+string(1,BOGGLE[nx][ny]),depth+1);
        visited[nx][ny] = false;
    }
}


void solve(){
    init();
    
    for(int i=0;i<4;i++){
        string boggl;
        cin>>boggl;
        for(int j=0;j<4;j++){
            BOGGLE[i][j] = boggl[j];
        }
    }
    
    for(int x=0;x<4;x++){
        for(int y=0;y<4;y++){
            string word = string(1,BOGGLE[x][y]);
            visited[x][y] = true;
            DFS(x,y,word,0);
            visited[x][y] = false;
        }
    }
    cout<<mxScore<<" "<<longestWord<<" "<<totalWordNum<<"\n";
}

int main(){
    cin.tie(0);
    cout.tie(0);
    ios::sync_with_stdio(0);
    
    input();
    for(int q=0;q<b;q++){
        solve();
    }
}