BOJ : 9202 Boggle

---

[BOJ 9202(P5)리뷰]

간단해 보이지만 간단하지 않은 문제다.

사용자로 부터 미리 N개의 단어를 입력받는다. 

그리고 4X4크기의 보드를 입력받는다.

이 보드에서 가로,세로,대각선으로 이동하며 만들 수 있는 단어의 개수, 단어의 총 점수(단어의 길이마다 점수가 있다.), 가장 긴 단어를 출력해야 한다.

보드에서 단어를 찾는것 + 미리 입력받은 N개(최대 30만개) 의 단어목록에 있는지 확인하는 작업을 완전탐색으로 하려면 내가 늙어 죽을때 까지 돌려도 찾기가 힘들것이다. 

따라서 이 문제를 해결하기 위해서는 "트라이"라는 자료구조에 대해 알아야 한다.

출처 : ko.wikipedia.org

트라이는 위 그림과 같은 구조를 갖고있다.

각각의 노드는 객체로 이루어져있으며 객체는  a~z 또는 A~Z의 26개의 동일한 객체를 갖는 구조로 되어있다.

단어의 삽입과 검색은 O(N)의 시간복잡도를 가지지만, 단어의 개수가 많을수록 엄청난 효율을 자랑한다.

즉 1개의 단어만 찾으려 한다면 오히려 메모리를 더 차지하는 별 의미가 없는 자료구조이지만, 여러개의 단어를 찾고자 할때 (EX. AA로 시작하는 모든 단어를 검색) 매우 효율적인 자료구조이다.

이 문제는 이 트라이구조를 이용하여 해결할 수 있다. 만약(0,0)인 A에서 단어 DFS를 통해 단어 탐색을 시작할 때 루트노드에 A로 시작하는 객체가 존재하지 않는다면 굳이 A부터 탐색할 필요가 없다.

만약 A가 존재하고, 그 다음 단어를 찾으려고 할때에도 현재 노드의 자식노드를 확인하여 가고자 하는 단어가 존재할때만 가도록 할 수 있다. 이 문제는 이 방법을 이용하면 된다.

결론적으로 이 문제는 DFS문제이지만, DFS하는 과정 중 트라이를 이용하여 방문 할 필요가 없는 위치에 대해 방문하지 않도록 하여 해결해야 하는 문제이다.

 

/*
	21.01.14
	BOJ : 9202 Boggle (https://www.acmicpc.net/problem/9202)
	자료구조/트라이
*/
#include <bits/stdc++.h>
using namespace std;

class Node {
public:
	Node* child[26];
	bool isEnd = false;
	bool isHit = false;
	int length = 0;

	Node() { memset(child, NULL, sizeof(child)); }
	void clearHit() {
		isHit = false;
		for (int i = 0; i < 26; i++) {
			if (child[i] != NULL) {
				child[i]->clearHit();
			}
		}
	}
};

Node root;
int score[10] = { 0,0,0,1,1,2,3,5,11,0 };
char board[4][4];
bool vis[4][4];
int dx[8] = { -1,-1,0,1,1,1,0,-1 };
int dy[8] = { 0,-1,-1,-1,0,1,1,1 };
int totalScore = 0;
string maxWord;
string currentWord;
int maxWordLength = 0;
int totalCount = 0;

void insert(string word) {
	Node* current = &root;

	int len = word.size();
	for (int i = 0; i < len; i++) {
		int wordIndex = word[i] - 'A';
		if (current->child[wordIndex] == NULL) {
			current->child[wordIndex] = new Node;
		}
		current = current->child[wordIndex];
	}
	current->isEnd = true;
	current->length = len;
}

void dfs(int r, int c, Node* cur) {
	if (cur == NULL) return;
	vis[r][c] = 1;

	if (cur->isEnd) { //단어가 완성되는 시점에서
		if (!cur->isHit) { //단어가 아직 Hit되지 않았을 경우
			totalCount++;
			totalScore += score[cur->length];
			if (cur->length >= maxWordLength) {
				if (cur->length == maxWordLength) { //길이가 같다면 사전순으로 앞서는 단어 선택
					if (currentWord < maxWord) {
						maxWord = currentWord;
					}
				}
				else {
					maxWordLength = cur->length;
					maxWord = currentWord;
				}
			}
			cur->isHit = true;
		}
	}
	
	for (int dir = 0; dir < 8; dir++) {
		int nx = r + dx[dir];
		int ny = c + dy[dir];
		int nxt = board[nx][ny] - 'A';
		if (nx < 0 || ny < 0 || nx >= 4 || ny >= 4 || vis[nx][ny]) continue;
		currentWord.append(string(1, board[nx][ny]));
		dfs(nx, ny, cur->child[nxt]);
		currentWord.erase(currentWord.size() - 1);
	}

	vis[r][c] = 0;
}

int main() {
	cin.tie(0);
	ios::sync_with_stdio(0);

	int N, T;
	cin >> N;

	for (int i = 0; i < N; i++) {
		string str;
		cin >> str;
		insert(str);
	}

	cin >> T;

	while (T--) {
		for (int i = 0; i < 4; i++) {
			for (int j = 0; j < 4; j++) {
				cin >> board[i][j];
			}
		}

		maxWord.clear();
		root.clearHit();
		maxWordLength = 0;
		totalScore = 0;
		totalCount = 0;

		for (int i = 0; i < 4; i++) {
			for (int j = 0; j < 4; j++) {
				int nxt = board[i][j] - 'A';
				currentWord.append(string(1, board[i][j]));
				dfs(i, j, root.child[nxt]);
				if (currentWord.size() > 0) currentWord.clear();
			}
		}

		cout << totalScore << " " << maxWord << " " << totalCount << '\n';
	}

	return 0;
}