[백준] 9202번 Boggle

9202번: Boggle

단어 사전을 만들 때

트라이 알고리즘을 이용하여 트리를 만들면

트리 생성 시 O(L*M), 탐색 시 O(L)

(L : 제일 긴 문자열의 길이, M : 총 문자열의 수)

로 빠르게 문자열을 탐색할 수 있다.

 

Boggle 보드의 모든 칸마다

가로, 세로, 대각선으로 인접한 칸을 DFS로

글자 수 1부터 8까지 탐색한다.

 

탐색하면서 사전에 이 단어가 있는지 찾는데

해당 단어가 있다면

set에 있는 단어인지 체크해준 뒤

(중복 찾기 방지 위해)

 

set에 있는 단어이면 이미 찾았던 단어이므로 그냥 넘어가고

set에 없는 단어라면 처음 찾는 단어이므로

글자 수에 맞게 점수를 더하고 찾은 단어의 개수를 + 1 해준다.

 

자료 구조의 기본도 안 돼있는 상태에서

트라이를 구현하려니 너무 힘들었다.

클래스와 포인터의 기초부터 공부해서 겨우 풀었지만

보통 char형으로 구현하던데

char는 도저히 다루기 힘들어서

친숙하고 쉬운 string으로 푼 게 마음에 걸린다.

#include <iostream>
#include <cstring>
#include <set>
#include <algorithm>
#include <string>
using namespace std;
int N, B, len, word_cnt, res;
int dx[8] = { -1, -1, -1, 0, 0, 1, 1, 1 }, dy[8] = { -1, 0, 1, -1, 1, -1, 0, 1 }, score[9] = { 0, 0, 0, 1, 1, 2, 3, 5, 11 };
string word, a, longgest;
class Trie {
public:
	Trie *node[26];
	bool finish;
	Trie() { // 멤버 변수 초기화
		this->finish = false;
		memset(node, NULL, sizeof(node));
	}
	void Insert(string key, int idx) {
		if (key[idx] == NULL) finish = true; // 빈 문자열이면 끝난 문자열이므로 종료 노드로 지정
		else {
			int next = key[idx] - 'A';
			if (node[next] == NULL) node[next] = new Trie(); // 현재 연결된 노드가 없는 경우 노드 생성
			node[next]->Insert(key, idx + 1); // 다음 문자열로 넘어감
		}
	}
	bool Find(string key, int idx) {
		if (key[idx] == NULL) { // 문자열 끝까지 잘 탐색했을 때
			if (finish) return true; // 찾는 문자열이 종료 노드면 찾기 성공
			return false; // 종료 노드가 아니면 없는 문자열이므로 실패
		}
		int current = key[idx] - 'A';
		if (node[current] == NULL) return false; // 생성되지 않은 노드가 존재하면 이 문자열은 없는 문자열이므로 실패
		return node[current]->Find(key, idx + 1); // 다음 문자열로 넘어감
	}
}trie;

set <string> s; // 중복 막기 위해

void Dfs(int X, int Y, string word, int cnt, string boggle[][5], bool visited[][5]) {
	if (cnt == 9) return;
	if (trie.Find(word, 0)) { // 현재 단어를 찾았고
		if (s.find(word) == s.end()) { //현재 단어가 중복이 아니라면
			s.insert(word); // 중복을 막아주기 위해 set 생성
			word_cnt++, res += score[cnt];
			if (longgest.size() < cnt) longgest = word;
			else if (longgest.size() == cnt) longgest = min(longgest, word);
		}
	}
	for (int i = 0; i < 8; i++) {
		int x = X + dx[i], y = Y + dy[i];
		if (x >= 0 && x < 4 && y >= 0 && y < 4 && !visited[x][y]) {
			visited[x][y] = true;
			word += boggle[x][y];
			Dfs(x, y, word, cnt + 1, boggle, visited);
			visited[x][y] = false;
			word.resize(word.size() - 1);
		}
	}
}


int main() {
	cin >> N;
	for (int i = 0; i < N; i++) {
		cin >> word;
		trie.Insert(word, 0);
	}
	cin >> B;
	for (int b = 0; b < B; b++) {
		string boggle[5][5];
		bool visited[5][5] = { false };
		for (int i = 0; i < 4; i++) {
			cin >> a;
			for (int j = 0; j < 4; j++) boggle[i][j] = a[j];
		}
		for (int i = 0; i < 4; i++) {
			for (int j = 0; j < 4; j++) {
				visited[i][j] = true;
				Dfs(i, j, boggle[i][j], 1, boggle, visited);
				visited[i][j] = false;
			}
		}
		cout << res << " " << longgest << " " << word_cnt << "\n";
		res = 0, longgest = "", word_cnt = 0, s.clear();
	}
	return 0;
}