C++ / 백준 / 9202 / Boggle

문제

 

https://www.acmicpc.net/problem/9202

9202번: Boggle

문제풀이

 

트라이 + DFS(백트래킹)로 풀었다.

입력이 들어오면 문자열들을 트라이로 구성한다.

그다음 DFS로 모든 경우의 수를 따지면 된다.

 

 

unordered_set<string>dict;
unordered_set<string>target;
int max_score;
string max_str;

vector<vector<char>>board;
vector<vector<bool>>visited;

int dy[8] = { -1,-1,-1,0,0,1,1,1 };
int dx[8] = { -1,0,1,-1,1,-1,0,1 };
int score[9] = { 0,0,0,1,1,2,3,5,11 };

target은 입력받은 단어를 저장하는 unordered_set이다. 문제에서 나오는 단어 사전을 의미한다.

dict은 현재 주어진 4x4크기의 그리드에서 DFS를 통해 문자를 구성하고 target과 같은 문자열들을 저장하는 set이다.

(매 테스트 케이스마다 초기화)

 

max_score은 최대 점수변수이다.

max_str은 최장 길이의 string을 저장하는 변수이다.

 

board는 4x4 크기의 그리드를 나타내는 2차원 벡터이다.

visited는 4x4 크기의 방문 벡터이다.

 

현재 위치에서 8가지 방향을 탐색해야 하므로 dy, dx는 8 크기의 배열이다.

문제에서 주어진 글자수에 따른 점수를 score를 통해 나타냈다.

 

메인문에서는 모든 입력을 받고 테스트케이스를 입력받는다.

그다음 4x4 그리드 하나하나씩 돌면서 DFS를 실행한다.

 

 

	void insert(string& str) {
		Trie* now = this;
		for (int idx = 0; idx < str.size(); ++idx) {			
			if (now->child[str[idx] - 'A'] == nullptr) {
				now->child[str[idx] - 'A'] = new Trie();
			}
			now = now->child[str[idx] - 'A'];
			if (idx == str.size() - 1) 	now->isEnd = true;
		}
	}

트라이의 insert 함수이다.

트라이의 자녀 트라이가 없으면 새로 생성해 주고, 문자의 끝이라면 isEnd를 true로 바꾼다.

 

void findWord(int y, int x, Trie* trie, string str) {
	for (int idx = 0; idx < 8; ++idx) {		
		int ny = y + dy[idx];
		int nx = x + dx[idx];
		if (ny < 0 || ny >= 4 || nx < 0 || nx >= 4) continue;
		if (visited[ny][nx] == true) continue;
		if (trie->child[board[ny][nx]-'A'] != nullptr) {
			string nstr = str;
			nstr += board[ny][nx];			
			Trie* ntrie = trie->child[board[ny][nx] - 'A'];			
			if (ntrie->isEnd == true) {
				if (target.find(nstr) != target.end() && dict.find(nstr) == dict.end()) {
					dict.insert(nstr);
					max_score += score[nstr.size()];
					if (max_str.size() == nstr.size()) {
						if (max_str > nstr) max_str = nstr;
					}
					else if (max_str.size() < nstr.size()) max_str = nstr;
				}
			}
			visited[ny][nx] = true;			
			findWord(ny, nx, ntrie, nstr);
			visited[ny][nx] = false;
		}
	}
}

DFS 함수이다.

인자로는 y, x, 트라이, 문자열을 받는다.

8가지 방향으로 탐색하면서 범위를 벗어나거나 방문한 적이 있으면 continue를 한다.

만약 다음칸이 자녀 트라이중에 있다면 문자열의 끝인지 확인을 한다.

 

문자열의 끝이라면 target에 있는지, 전에 구했던 문자열이 아닌지를 확인한다.

새로운 문자열이고 target에 있는 문자열이라면 max_score에 점수를 더하고, 현재 문자열이 최장 길이의 문자열인지 판별하고 맞다면 max_str을 갱신한다.

 

그다음 다시 DFS함수를 실행한다.

모든 경우를 탐색할 때까지 위의 과정을 반복한다.

 

코드

 

#include <bits/stdc++.h>
using namespace std;

unordered_set<string>dict;
unordered_set<string>target;
int max_score;
string max_str;

vector<vector<char>>board;
vector<vector<bool>>visited;

int dy[8] = { -1,-1,-1,0,0,1,1,1 };
int dx[8] = { -1,0,1,-1,1,-1,0,1 };
int score[9] = { 0,0,0,1,1,2,3,5,11 };

struct Trie {
	Trie* child[26];
	bool isEnd;

	Trie() : child(), isEnd(false) {}

	~Trie() {
		for (int idx = 0; idx < 26; ++idx)
			if (child[idx]) delete child[idx];
	}

	void insert(string& str) {
		Trie* now = this;
		for (int idx = 0; idx < str.size(); ++idx) {			
			if (now->child[str[idx] - 'A'] == nullptr) {
				now->child[str[idx] - 'A'] = new Trie();
			}
			now = now->child[str[idx] - 'A'];
			if (idx == str.size() - 1) 	now->isEnd = true;
		}
	}
};

void findWord(int y, int x, Trie* trie, string str) {
	for (int idx = 0; idx < 8; ++idx) {		
		int ny = y + dy[idx];
		int nx = x + dx[idx];
		if (ny < 0 || ny >= 4 || nx < 0 || nx >= 4) continue;
		if (visited[ny][nx] == true) continue;
		if (trie->child[board[ny][nx]-'A'] != nullptr) {
			string nstr = str;
			nstr += board[ny][nx];			
			Trie* ntrie = trie->child[board[ny][nx] - 'A'];			
			if (ntrie->isEnd == true) {
				if (target.find(nstr) != target.end() && dict.find(nstr) == dict.end()) {
					dict.insert(nstr);
					max_score += score[nstr.size()];
					if (max_str.size() == nstr.size()) {
						if (max_str > nstr) max_str = nstr;
					}
					else if (max_str.size() < nstr.size()) max_str = nstr;
				}
			}
			visited[ny][nx] = true;			
			findWord(ny, nx, ntrie, nstr);
			visited[ny][nx] = false;
		}
	}
}

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

	int w(0);
	cin >> w;
	Trie* trie = new Trie();	
	string word("");

	for (int idx = 0; idx < w; ++idx) {
		cin >> word;
		target.insert(word);
		trie->insert(word);
	}		
	
	int T(0);	
	
	cin >> T;
	for (int test_case = 1; test_case <= T; ++test_case) {
		board = vector<vector<char>>(4, vector<char>(4, ' '));
		visited = vector<vector<bool>>(4, vector<bool>(4, false));
		dict.clear();
		max_score = 0;
		max_str.clear();

		for (int y = 0; y < 4; ++y) {
			for (int x = 0; x < 4; ++x) {
				cin >> board[y][x];
			}
		}

		for (int y = 0; y < 4; ++y) {
			for (int x = 0; x < 4; ++x) {
				string str("");
				str += board[y][x];
				visited[y][x] = true;
				if (trie->child[board[y][x] - 'A'] != nullptr) {					
					Trie* ntrie = trie->child[board[y][x] - 'A'];					
					findWord(y, x, ntrie, str);
				}
				visited[y][x] = false;
			}
		}
		cout << max_score << " " << max_str << " " << dict.size() << '\n';
	}
}