[BOJ/9202] Boggle, c++

🔗 링크

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

9202번: Boggle

https://github.com/jokj624/PS/blob/master/5000-10000/9202.cpp

jokj624/PS

🤯 한줄 후기

한줄 후기 : 와 역대급 힘들었던 문제 

알고 접기 실패

🤷 문제

👩‍💻 풀이

스터디에서 푼 문제이다.

트리 문제인걸 보고 들어간터여서 바로 생각 났던건 트라이 자료구조였다.

그런데 풀어본 적은 없고, 단어를 저장하는 트리, 빠르게 검색하는 트리 정도로만 알고 있었음.

같이 하는 친구들한테 단어들을 트라이 트리에 저장해 놓고, 밑에 보드판은 dfs로 탐색 하면서 찾는 게 어떻냐고 했다.

거의 맞는 거 같긴 했는데 트라이 문제를 풀어본 적이 없어서 어떻게 할지 막막했다.

 

일단 트라이 자료구조를 속성으로 구글링해서 익히고, c++ 코드를 보며 짰다. 

https://it-and-life.tistory.com/166

[자료구조] 트리(Tree) - 트라이 트리(Trie tree)

참고한 블로그

트라이 트리의 검색 시간복잡도는 저장된 단어 길이 중 최대를 M이라 할때, O(M) 이라고 한다. 

 

얼추 구성을 했고, 보드판 탐색을 진행했는데 처음에 모든 칸에서 한번씩 dfs를 돌리면 TLE가 발생할까봐 보드판 한개당 한번만 돌게끔 구성을 했더니 만들 수 없었다. 

그래서 그냥 4X4 16칸에서 모두 한번씩 dfs를 돌리는 방향으로 구현했다.

시간이 10초라 완전 탐색해도 괜찮다.

 

dfs를 호출할 때, word에 한 문자씩 더해가며 단어 길이가 8을 넘지 않을 때 까지만 트라이 트리에서 search 해줬다.

단어가 중복되면 하나만 센 걸로 쳐야하는데 이는 set에 저장해 해결했다.

중복된 단어가 없을 때만 set에 insert하는 방식을 사용했다.

???

뭔데요..?

예제 맞고, 접근법 완벽해보였는데 

결국 새벽까지 이리저리 코드를 고치다가 자고 오늘 다시 풀어서 힘겹게 AC를 받았다.

 

구글링하다가 한 블로그에서 반례를 발견했는데

https://dlwnsdud205.tistory.com/120 

[백준 / BOJ] 9202 Boggle

이 분 블로그에서 발견했다.

트라이 자료구조를 잘못 만든 거였다.

 

3

ABC
AB
A

 

1

ABCX
XXXX
XXXX
XXXX

 

답이 1 ABC 3 인데 난 1 ABC 1이 떴다.

 

처음 제출한 코드에서 잘못된 부분을 발견했다. 혹시나 저랑 똑같은데 혼자 고쳐보고 싶으신 분들은 더보기 누르지 마시고,,

bool findWord(string str, int idx, Node* node){
		if(!node->child.empty() && idx >= str.length())	return false;
		if(idx >= str.length())	return true;
		int next = -1;
		for(int i=0; i<node->child.size(); i++){
			if(str[idx] == node->child[i]->data){
				next = i;
				break;
			}
		}
		if(next != -1)	return findWord(str,idx+1,node->child[next]); // 동일 문자 존재 
		else	return false; //검색 실패
}

void insert(string str, int idx, Node* node){
		if(idx >= str.length())	return;
		int next = -1;
		for(int i=0; i<node->child.size(); i++){
			if(str[idx] == node->child[i]->data){
				next = i;
				break;
			}
		}
		if(next != -1){
			insert(str, idx+1, node->child[next]);
		}
		else{
			Node* newNode = new Node;
			newNode->data = str[idx];
			node->child.push_back(newNode);
			insert(str, idx+1, newNode);
		}
}

나는 단어 전체를 저장하지 않고 있어서 만약 ABC가 먼저 들어오면 AB, A는 search에서 첫번째 행에 의해 바로 false를 리턴한 것이였다.

따라서 Node class에 단어 전체를 저장할 변수를 만들어 주고, insert할 때, 해당 위치 노드에 strData 변수에 단어 전체를 넣어줘 해결할 수 있었다.

💻 코드

//AC
//BOJ 9202 Boggle
#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <set>
using namespace std;
int dx[8] = {0, 0, 1, -1, -1, -1, 1, 1};
int dy[8] = {1, -1, 0, 0, 1, -1, 1, -1};
set<string> ans;
string map[4], wordMax;
bool visit[4][4];
int wordSizeMax = 0;
int maxScore = 0;
class Node {
	public:
		char data;    //문자 저장 변수
		string strData;   // 단어 저장할 변수
		vector<Node*> child;
};
class Trie{
	private:
		Node* root = new Node;
	public:
		void push(string str){
			insert(str, 0, root);
		}
		void insert(string str, int idx, Node* node){
			if(idx >= str.length()){
				node->strData = str;   // 단어 저장
				return;
			}
			int next = -1;
			for(int i=0; i<node->child.size(); i++){
				if(str[idx] == node->child[i]->data){
					next = i;
					break;
				}
			}
			if(next != -1){
				insert(str, idx+1, node->child[next]);
			}
			else{
				Node* newNode = new Node;    //해당 문자 없다면 노드 새로 생성
				newNode->data = str[idx];
				node->child.push_back(newNode);
				insert(str, idx+1, newNode);
			}
		}
		bool search(string str){
			return findWord(str, 0, root);
		}
		bool findWord(string str, int idx, Node* node){
			if(!node->child.empty() && idx >= str.length())	{
				if(node->strData == str)	return true;    //리프노드는 아니지만 해당 단어가 존재하는 곳
				else	return false;	
			}
			if(idx >= str.length())	return true;  // 리프노드
			int next = -1;
			for(int i=0; i<node->child.size(); i++){
				if(str[idx] == node->child[i]->data){
					next = i;
					break;
				}
			}
			if(next != -1)	return findWord(str,idx+1,node->child[next]); // 동일 문자 존재 
			else	return false; //검색 실패
		}
};
Trie* trie = new Trie;
int score(int size){
	switch (size){
		case 1: 
		case 2:
			return 0;
			break;
		case 3:
		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;
	}
	return 0;
}
void dfs(int x, int y, string word){
	if(visit[x][y])	return;  //이미 방문
	if(word.size() > 8){  //8자리 단어가 최대
		return;
	}
	if(trie->search(word)){   // 단어 존재 여부 검사
		if(ans.find(word) == ans.end()){  // 단어 중복 여부 검사
			ans.insert(word);  // set에 삽입
			maxScore += score(word.length());   //점수 합계
			if(word.length() > wordSizeMax){   // 더 긴 단어 찾기
				wordSizeMax = word.length();
				wordMax = word;   
			}
			else if(word.length() == wordSizeMax){
				wordMax = min(wordMax, word);   //사전 순 
			}
		}
	}
	visit[x][y] = true;
	for(int i=0; i<8; i++){
		int nx = x+dx[i];
		int ny = y+dy[i];
		if(nx < 0 || ny < 0 || nx >= 4|| ny >= 4)	continue;
		word += map[nx][ny];  
		dfs(nx, ny, word);
		word.pop_back();
	}
	visit[x][y] = false; 
}
int main(){
	ios::sync_with_stdio(false);
	cin.tie(NULL);

	int w, b;
	cin >> w;
	for(int i=0; i<w; i++){
		string s;
		cin >> s;
		trie->push(s);
	}

	cin >> b;
	for(int i=0; i<b; i++){
		for(int j=0; j<4; j++){
			cin >> map[j];
		}
		for(int m=0; m<4; m++){
			for(int n=0; n<4; n++){
				visit[m][n]  = false;
			}
		}
		ans.clear();
		wordSizeMax = 0; 	maxScore = 0;	wordMax.clear();
		for(int k=0; k<4; k++){ 
			for(int l=0; l<4; l++){
				string s;
				s.push_back(map[k][l]);
				dfs(k, l, s);
			}
		}
		cout << maxScore << " " << wordMax << " " << ans.size()<< "\n";
	}

	return 0;
}