백준 9202번 Boggle

🔒[문제 url]

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

🔑알고리즘

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

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

🐾부분 코드

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;

<변수 선언>
$b$의 범위는 30까지이므로, 3차원 배열 board를 선언한다.

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;
}

<답안 갱신 함수>
사전에 등재된 단어를 발견했다면, 최대 점수 , 가장 긴 단어 , 찾은 단어 갯수를 갱신한다. map의 bool 값또한 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;
	}
}

<DFS 함수>
인접한 8가지 방향으로 깊이 우선 탐색을 진행하며 문자열을 만들어나간다.
지금까지의 str에 현재 지점의 문자를 더한 후 등재 여부를 확인하므로, 지금까지의 str 길이가 8이라면 탐색을 종료한다.

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';
	}
}

<브루트포스>
시작 지점이 만들어나갈 문자열의 첫번째 글자가 되므로, 보드판 내의 모든 지점에 대해 DFS를 진행한다.
탐색 전 Init()에 주의하자.

🪄전체 코드

#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();
}

🥇문제 후기

실수를 남발하기 좋은 문제. 아이디어 자체 Platinum 난이도는 아니라고 생각하지만, 구현량이 적지않다보니 실수가 많이 유발되어 높게 책정된 것 같다.
재미있었다!