알고스팟 - 보글 게임 (BOGGLE) [C++]

 이 문제는 완전 탐색에 메모이제이션을 더한 다이나믹 프로그래밍으로 풀 수 있다. 완전 탐색으로 풀게 되면 시간 초과가 나게 되는데, 이를 메모이제이션으로 결괏값을 저장해주고, 저장되었다면 바로 리턴하도록 만들면 시간 안에 풀 수 있다.

 

#include <iostream>
#include <string>
#include <vector>

using namespace std;

#define BOARD_SIZE 5

char board[BOARD_SIZE][BOARD_SIZE];

int dy[] = { -1, 1, 0, 0, -1, -1, 1, 1 };
int dx[] = { 0, 0, -1, 1, -1, 1, -1, 1 };

int dp[BOARD_SIZE][BOARD_SIZE][11];

void init() {
	for (int y = 0; y < BOARD_SIZE; y++) {
		for (int x = 0; x < BOARD_SIZE; x++) {
			for (int i = 0; i < 11; i++) {
				dp[y][x][i] = -1;
			}
		}
	}
}

bool inRange(int y, int x) {
	if (0 <= y && y < BOARD_SIZE && 0 <= x && x < BOARD_SIZE) {
		return true;
	}
	return false;
}

int solve(string &word, int y, int x, int index) {
	if (index == word.size()) {
		return 1;
	}

	if (dp[y][x][index] != -1) {
		return dp[y][x][index];
	}

	for (int i = 0; i < 8; i++) {
		int ny = y + dy[i];
		int nx = x + dx[i];

		if (inRange(ny, nx) && word[index] == board[ny][nx]) {
			int result = solve(word, ny, nx, index + 1);

			if (result) {
				return dp[y][x][index] = 1;
			}
		}
	}

	return dp[y][x][index] = 0;
}

int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);

	int C;
	cin >> C;

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

		int N;
		cin >> N;
		
		for (int i = 0; i < N; i++) {
			string word;
			cin >> word;

			init();

			int result = 0;
			for (int y = 0; y < BOARD_SIZE; y++) {
				for (int x = 0; x < BOARD_SIZE; x++) {
					if (word[0] == board[y][x]) {
						result = solve(word, y, x, 1);

						if (result) {
							break;
						}
					}
				}

				if (result) {
					break;
				}
			}

			cout << word << " ";
			if (result) {
				cout << "YES" << '\n';
				continue;
			}
			cout << "NO" << '\n';
		}
	}

	return 0;
}