[Algospot] 보글 게임 (문제ID:BOGGLE)

문제

보글(Boggle) 게임은 그림 (a)와 같은 5x5 크기의 알파벳 격자인
게임판의 한 글자에서 시작해서 펜을 움직이면서 만나는 글자를 그 순서대로 나열하여 만들어지는 영어 단어를 찾아내는 게임입니다. 펜은 상하좌우, 혹은 대각선으로 인접한 칸으로 이동할 수 있으며 글자를 건너뛸 수는 없습니다. 지나간 글자를 다시 지나가는 것은 가능하지만, 펜을 이동하지않고 같은 글자를 여러번 쓸 수는 없습니다.

예를 들어 그림의 (b), (c), (d)는 각각 (a)의 격자에서 PRETTY, GIRL, REPEAT을 찾아낸 결과를 보여줍니다.

보글 게임판과 알고 있는 단어들의 목록이 주어질 때, 보글 게임판에서 각 단어를 찾을 수 있는지 여부를 출력하는 프로그램을 작성하세요.

 

입력

입력의 첫 줄에는 테스트 케이스의 수 C(C <= 50)가 주어집니다. 각 테스트 케이스의 첫 줄에는 각 5줄에 5글자로 보글 게임판이 주어집니다. 게임판의 모든 칸은 알파벳 대문자입니다.
그 다음 줄에는 우리가 알고 있는 단어의 수 N(1 <= N <= 10)이 주어집니다. 그 후 N줄에는 한 줄에 하나씩 우리가 알고 있는 단어들이 주어집니다. 각 단어는 알파벳 대문자 1글자 이상 10글자 이하로 구성됩니다.

 

출력

각 테스트 케이스마다 N줄을 출력합니다. 각 줄에는 알고 있는 단어를 입력에 주어진 순서대로 출력하고, 해당 단어를 찾을 수 있을 경우 YES, 아닐 경우 NO를 출력합니다.

---

완전 탐색으로만 풀려고 하다가 시간 초과로 틀린 문제. 메모이제이션이 필요했다.

memo 배열은 (x,y)에 길이가 z일때를 방문 했는지 안 했는지를 검사한다. 방문한 적이 있으면 1이고 없으면 0이다.

그래서 입력 문자열의 끝까지 모두 조사를 마쳤으면 isTrue를 true로 전환하고 종료한다.

참고로 배열을 초기화 하는 memset은 <memory.h>에 포함되어있는데

또 <memory.h>는 <string.h>에 포함되어 있으므로 아무거나 사용해도 무방하다.

<cstring>을 포함해도 사용 가능하다.

 

코드 원본 : https://github.com/chosh95/STUDY/blob/master/Algospot/BOGGLE.cpp

C++ 코드 : 

#include <iostream>
#include <string>
#include <memory.h>
using namespace std;
int C, N;
string res;
char p[6][6];
bool isTrue;
int dx[8] = { -1,0,1,1,1,0,-1,-1 };
int dy[8] = { 1,1,1,0,-1,-1,-1,0 };
int memo[6][6][11];
void dfs(int x, int y, int cnt) {
	if (p[x][y] != res[cnt]) return;
	if (res.length() == cnt + 1) {
		isTrue = true;
		return;
	}
	for (int i = 0; i < 8; i++) {
		int nx = x + dx[i];
		int ny = y + dy[i];
		if (nx < 1 || nx >5 || ny < 1 || ny>5) continue;
		if (p[nx][ny] != res[cnt + 1]) continue;
		if (memo[nx][ny][cnt + 1] == 1) continue;
		memo[nx][ny][cnt + 1] = 1;
		dfs(nx, ny, cnt + 1);
	}
}
int main()
{
	cin >> C;
	while (C--) {
		for (int i = 1; i < 6; i++) {
			string str;
			cin >> str;
			for (int j = 1; j < 6; j++) {
				p[i][j] = str[j - 1];
			}
		}
		cin >> N;
		while (N--) {
			memset(memo, 0,sizeof(memo));
			cin >> res;
			isTrue = false;
			for (int i = 1; i <= 5; i++) {
				if (isTrue) break;
				for (int j = 1; j <= 5; j++) {
					if (p[i][j] == res[0]) {
						memo[i][j][0] = 1;
						dfs(i, j, 0);
					}
					else continue;
				}
			}
			cout << res;
			if (isTrue) cout << " YES\n";
			else cout << " NO\n";
		}
	}
}