백준 9202 Boggle

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

9202번: Boggle

 

문제 접근법 : 

처음 set을 이용해서 푸는 문젠줄 알았는데 안되더군요

좀더 효과적인 알고리즘이 필요했는데

Trie를 이용한 문제더군요 

모든 단어를 trie로 나열하고

 

보드안에 있는 좌표를 처음부터 시작해서 마지막까지 만들수있는 모든경우의수를

전부 만듭니다. 그렇지만 만들필요가 없는 단어가 시작되지도 않는다면

그런 경우의수 같은 것은 제외해야겠죠?

 

소스코드 : 

#include <bits/stdc++.h>
using namespace std;
int n,b;
int check[5][5];
int dy[8]={-1,-1,-1,0,0,1,1,1};
int dx[8]={-1,0,1,-1,1,-1,0,1};
int score[]={0,0,0,1,1,2,3,5,11};
set<string> res;
vector<string> Board[30];
bool isrange(int y,int x){
	return 0<=y&&y<4&&0<=x&&x<4;
}
class trie{
	public:
	trie *alpha[26]={0};
	bool terminal=false;
	trie(){
		memset(alpha,0,sizeof(alpha));
		terminal=false;
	}
	void insert(string &s,int idx=0)
	{
		if(s[idx]==0){
			terminal = true;
			return;
		}
		int next = s[idx]-'A';
		if(alpha[next]==NULL)
			alpha[next]=new trie();
		alpha[next]->insert(s,idx+1);
	}
	void find(vector<string> &board,int y,int x,string s){
		if(s.size()>8)return;
		check[y][x]=1;
		trie * t = this->alpha[board[y][x]-'A'];
		if(t->terminal){
			res.insert(s);
		}
		for(int i=0;i<8;i++){
			int ny=y+dy[i];
			int nx=x+dx[i];
			if(isrange(ny,nx)&&check[ny][nx]==0&&t->alpha[board[ny][nx]-'A']){
				t->find(board,ny,nx,s+board[ny][nx]);
			}
		}
		check[y][x]=0;
	}
};
trie root;
void input(){
	cin>>n;
	string is;
	for(int i=0;i<n;i++){
		cin>>is;
		root.insert(is);
	}
	cin>>b;
	for(int i=0;i<b;i++){
		res.clear();
		for(int j=0;j<4;j++){
			cin>>is;
			Board[i].push_back(is);
		}
	}
}
void solve(){
	for(int k=0;k<b;k++){
		res.clear();
		int Max=-1;
		string word="";
		for(int i=0;i<4;i++){
			for(int j=0;j<4;j++){
				if(root.alpha[Board[k][i][j]-'A'])
					root.find(Board[k],i,j,Board[k][i].substr(j,1));
			}
		}
		int total=0;
		for(string s:res){
			total+=score[s.size()];
			if(score[s.size()]>Max){
				Max=score[s.size()];
				word = s;
			}
			else if(score[s.size()]==Max){
				word = word<s?word:s;
			}
		}
		cout<<total<<" "<<word<<" "<<res.size()<<"\n";
	}
}
int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	//freopen("input.txt","r",stdin);
	input();
	solve();
}

 

 

 

답을 맞췄었도 시간이 4초나 걸려서 좀더 개선의 여지는 많이 있겠지만 

좀더 노력을 해야할것같네요

 

궁금한점 혹은 모르는점 어떤질문이든 댓글은 언제나 환영입니다.