문제

알고스팟 BOGGLE 게임

풀이

1. 무작정 풀기

#include <iostream>
#include <string>
#include <vector>
using namespace std;

const int BOARD_SIZE = 5;
auto board = vector<vector<char>>(BOARD_SIZE, vector<char>(BOARD_SIZE, '*'));

bool finding(int y, int x, string word, int n){
	if(n == word.size()) return true;

	for(int i = y-1; i <= y+1; i++)
		for(int j = x-1; j <= x+1; j++){
			if((i == y)&&(j == x) or i < 0 or i > BOARD_SIZE-1 or j < 0 or j > BOARD_SIZE-1)
				continue;
                
			if(board[i][j] == word[n]) {
				if(finding(i, j, word, n+1))
					return true;
			}
			
		}
	
	return false;

}


bool find_word(string word) {

	for(int i = 0; i < BOARD_SIZE; i++)	{
		for(int j = 0; j < BOARD_SIZE; j++) {		
			if(board[i][j] == word[0]) {
				if(finding(i, j, word, 1))
					return true;
			}
		}
	}
		
	return false;

}



int main () {
	int C;
	cin >> C;
	for(int i = 0; i < C; i++) {
		
		for(int i = 0; i < BOARD_SIZE; i++)	{
			for(int j = 0; j < BOARD_SIZE; j++) {		
				cin >> board[i][j];
			}
		}

		int N;
		cin >> N;


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

			cout << word << " " << (find_word(word) ? "YES" : "NO") << endl;
			
		}
	}
    
	return 0;

}

메모리와 시간초과를 고려하지 않고, 무작정 풀어보았다.

find_word 함수를 통하여 보드판에서 word 의 첫번째 알파벳과 일치하는 지점에서 finding 함수를 통하여 재귀가 시작 된다.

역시나 결과는 시간초과이다.

2. 동적 계획법

#include <iostream>
#include <string>
#include <vector>
using namespace std;

const int BOARD_SIZE = 5;
auto board = vector<vector<char>>(BOARD_SIZE, vector<char>(BOARD_SIZE, '*'));

int cache[BOARD_SIZE][BOARD_SIZE][10];

bool finding(int y, int x, string word, int n){
	
	if(n == word.size()) return true;

	int& ret = cache[y][x][n];
	
	if(ret == 1) {
		return false;
	} else {
		ret = 1;
	}

	for(int i = y-1; i <= y+1; i++)
		for(int j = x-1; j <= x+1; j++){
			if((i == y)&&(j == x) or i < 0 or i > BOARD_SIZE-1 or j < 0 or j > BOARD_SIZE-1)
				continue;

			if(board[i][j] == word[n]) {
				if(finding(i, j, word, n+1))
					return true;
			}
			
		}
	
	return false;

}


bool find_word(string word) {

	for(int i = 0; i < BOARD_SIZE; i++)	{
		for(int j = 0; j < BOARD_SIZE; j++) {		
			if(board[i][j] == word[0]) {
				if(finding(i, j, word, 1))
					return true;
			}
		}
	}
	return false;
}



int main () {
	int C;
	cin >> C;	

	for(int i = 0; i < C; i++) {
		
		for(int i = 0; i < BOARD_SIZE; i++)	{
			for(int j = 0; j < BOARD_SIZE; j++) {		
				cin >> board[i][j];
			}
		}

		int N;
		cin >> N;

		for(int i=0; i<N; i++) {
			memset(cache, -1, sizeof(cache));

			string word;
			cin >> word;

			cout << word << " " << (find_word(word) ? "YES" : "NO") << endl;
			
		}
	}

	return 0;

}

시간초과를 해결하기 위해 동적 계획법을 활용하였다. memset 함수를 통해 3차원 배열의 cache 를 초기화 하고, 각각의 단어를 찾는 과정에서 중복되는 과정을 제거하였다.

3차원 배열의 1, 2 차원은 보드판의 각각의 알파벳의 위치를 의미하며 3 차원의 배열은 그 알파벳이 한 단어에서 몇번째 위치에 오는가를 의미한다.

결과는 8 m/s 의 수행시간으로, 시간초과를 해결한 정답이다.