[백준/C++] 9202번 Boggle

문제

 

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

---

Algorithm

보드판의 각 지점에 대하여 DFS를 진행해 문자열을 만들어나간다.
현재까지 만들어진 문자열이 사전에 등재되어 있는 단어라면 최대 점수, 가장 긴 단어, 찾은 단어의 수를 갱신한다.

• 사전에 등재되어 있는 단어인 것은 어떻게 파악하는가?
  • 사전의 단어들이 정렬되어 있을 필요는 없으므로, unordered_map<string,bool> 자료구조를 활용한다.
• 탐색 종료 조건은?
  • 문제의 조건에 따라 단어의 길이는 최대 8글자이므로, 만들어진 문자열의 길이가 8을 초과한다면 종료한다.
• b개의 보드판을 탐색하게 되므로, 초기화에 주의한다.
  또한, 이미 발견한 단어에 대해서는 map의 bool 값을 true로 표시한다.

 

---

 

 

Code

#include <iostream>
#include <unordered_map>
#include <queue>
#include <memory.h>
using namespace std;
#define IAMFAST ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);

int w;
string word;
int b;
char board[31][4][4];

int scores[9] = {0,0,0,1,1,2,3,5,11};
pair<int,int> dir[8] = {{-1,0},{-1,1},
						{0,1},{1,1},
						{1,0},{1,-1},
						{0,-1},{-1,-1}};
bool visited[4][4];
unordered_map<string,bool> M;
int maxScore = 0;//최대 점수
string longest = "";//가장 긴 단어
int cnt = 0;

void INPUT()
{
	IAMFAST
	cin >> w;
	for(int i = 0; i < w; i++)
	{
		cin >> word;
		M.insert({ word, false });
	}
	cin >> b;
	for(int i = 0; i < b; i++)
		for(int j = 0; j < 4; j++)
			for(int k = 0; k < 4; k++)
				cin >> board[i][j][k];
}

void Init()
{
	memset(visited,false,sizeof visited);
	unordered_map<string,bool>::iterator it;
	for(it = M.begin(); it != M.end(); it++) it->second = false;
	maxScore = 0;
	longest = "";
	cnt = 0;
}

void setAns(string str)
{
	//최대 점수
	maxScore += scores[str.length()];
	//가장 긴 단어
	if(str.length() > longest.length()) longest = str;
	else if(str.length() == longest.length()) longest = min(str,longest);
	//찾은 단어의 갯수
	cnt++;

	M[str] = true;
}

void DFS(int tc,int x,int y,string str)
{
	if(str.length() == 8) return;

	str += board[tc][x][y];
	if(M.find(str)!=M.end()&&!M[str]) setAns(str);

	for(int i = 0; i < 8; i++)
	{
		int nx = x + dir[i].first;
		int ny = y + dir[i].second;
		if(!(0<=nx&&nx<4&&0<=ny&&ny<4)) continue;
		if(visited[nx][ny]) continue;

		visited[nx][ny] = true;
		DFS(tc,nx,ny,str);
		visited[nx][ny] = false;
	}
}

void SOLVE()
{
	for (int i = 0; i < b; i++)
	{
		Init();

		for (int j = 0; j < 4; j++)
			for (int k = 0; k < 4; k++)
				visited[j][k] = true,
				DFS(i, j, k, ""),
				visited[j][k] = false;
		cout << maxScore << " " << longest << " " << cnt << '\n';
	}
}

int main()
{
	INPUT();
	SOLVE();
}