[백준] 9202 Boggle

문제

상근이는 보드 게임 "Boggle"을 엄청나게 좋아한다. Boggle은 글자가 쓰여 있는 주사위로 이루어진 4×4 크기의 그리드에서 최대한 많은 단어를 찾는 게임이다. 

상근이는 한 번도 부인을 Boggle로 이겨본 적이 없다. 이렇게 질 때마다 상근이는 쓰레기 버리기, 설거지와 같은 일을 해야 한다. 이제 상근이는 프로그램을 작성해서 부인을 이겨보려고 한다.

Boggle에서 단어는 인접한 글자(가로, 세로, 대각선)를 이용해서 만들 수 있다. 하지만, 한 주사위는 단어에 한 번만 사용할 수 있다. 단어는 게임 사전에 등재되어 있는 단어만 올바른 단어이다.

1글자, 2글자로 이루어진 단어는 0점, 3글자, 4글자는 1점, 5글자는 2점, 6글자는 3점, 7글자는 5점, 8글자는 11점이다. 점수는 자신이 찾은 단어에 해당하는 점수의 총 합이다.

단어 사전에 등재되어 있는 단어의 목록과 Boggle 게임 보드가 주어졌을 때, 얻을 수 있는 최대 점수, 가장 긴 단어, 찾은 단어의 수를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 단어 사전에 들어있는 단어의 수 w가 주어진다. (1 < w < 300,000) 다음 w개 줄에는 단어가 주어진다. 단어는 최대 8글자이고, 알파벳 대문자로만 이루어져 있다. 단어 사전에 대한 정보가 모두 주어진 이후에는 빈 줄이 하나 주어진다.

그 다음에는 Boggle 보드의 개수 b가 주어진다. (1 < b < 30) 모든 Boggle은 알파벳 대문자로 이루어져 있고, 4줄에 걸쳐 주어진다. 각 Boggle의 사이에는 빈 줄이 하나  있다.

출력

각각의 Boggle에 대해, 얻을 수 있는 최대 점수, 가장 긴 단어, 찾은 단어의 개수를 출력한다. 한 Boggle에서 같은 단어를 여러 번 찾은 경우에는 한 번만 찾은 것으로 센다. 가장 긴 단어가 여러 개인 경우에는 사전 순으로 앞서는 것을 출력한다. 각 Boggle에 대해서 찾을 수 있는 단어가 적어도 한 개인 경우만 입력으로 주어진다.

 

 

찾아야하는 W개의 단어들로 트라이를 구성합니다.

 

그리고 N개의 4*4 그리드에서 dfs를 사용해서 한 주사위씩 접근합니다.

루트에서 시작하여 다음 단어에 접근가능하다면 dfs로 진행합니다.

 

#include<bits/stdc++.h>
#define FAST ios_base::sync_with_stdio(false),cin.tie(NULL);
#define mset(v) memset(v,0,sizeof(v));
#define rep(i,a) for(int i=0;i<a;++i)
#define REP(i,a) for(int i=1;i<=a;++i)

using namespace std;

typedef long long ll;
typedef pair<int, int> pi;
typedef tuple<int, int, int>ti;
typedef vector<int> vi;
typedef vector<vector<int>> vvi;
int dy[] = { -1,-1,0,1,1,1,0,-1 }, dx[] = {0,1,1,1,0,-1,-1,-1}, INF = 987654321;

struct Trie {
	bool output;
	Trie* go[26];
	Trie() {
		fill(go,go+26, nullptr);
		output = false;
	}
	void insert(string key) {
		if (!key.length()) {
			return;
		}
		int c = key[0] - 'A';
		if (!go[c]) {
			Trie* temp = new Trie;
			go[c] = temp;
		}
		if (key.length() == 1)go[c]->output = true;
		go[c]->insert(key.substr(1));
	}
};
int v[5][5];
int N, W;
char mp[5][5];
vector<string>ans;
int getscore(string key) {
	switch (key.length()) {
	case 1:
		return 0;
		break;
	case 2:
		return 0;
		break;
	case 3:
		return 1;
		break;
	case 4:
		return 1;
		break;
	case 5:
		return 2;
		break;
	case 6:
		return 3;
		break;
	case 7:
		return 5;
		break;
	case 8:
		return 11;
		break;
	}
}
void dfs(int y, int x, Trie* cur,string str) {
	if (v[y][x])return;
	if (cur->output)ans.push_back(str);
	v[y][x] = 1;
	rep(i, 8) {
		int ny = y + dy[i];
		int nx = x + dx[i];
		if (ny>=1 && ny<=4 && nx>=1 && nx<=4 && cur->go[mp[ny][nx] - 'A'] && !v[ny][nx]) {
			dfs(ny, nx, cur->go[mp[ny][nx]-'A'], str + mp[ny][nx]);
		}
	}
	v[y][x] = 0;
}
int main() {
	FAST;
	cin >> N;
	Trie* root = new Trie;
	REP(i, N) {
		string str;
		cin >> str;
		root->insert(str);
	}
	cin >> W;
	while (W--) {
		ans.clear();
		REP(i, 4)REP(j, 4)cin >> mp[i][j];
		REP(i, 4)REP(j, 4) {
			if (root->go[mp[i][j] - 'A']) {
				mset(v);
				string temp;
				temp.push_back(mp[i][j]);
				dfs(i, j, root->go[mp[i][j] - 'A'],temp);
			}
		}
		sort(ans.begin(), ans.end());
		ans.erase(unique(ans.begin(), ans.end()), ans.end());
		int score = 0, len = 1, idx = 0;
		for (int i = 0; i < ans.size(); i++) {
			score += getscore(ans[i]);
			if (ans[i].length() > len) {
				len = ans[i].length();
				idx = i;
			}
		}
		if(ans.size())
			cout << score << " " << ans[idx] << " " << ans.size() << "\n";
		else {
			cout << "0 0";
		}
	}
	delete root;
}