[C++]algospot BOGGLE

문제 링크 : https://www.algospot.com/judge/problem/read/BOGGLE

algospot.com :: BOGGLE

 

작년에 이 문제를 풀어봤었지만, 시간 초과로 해결하지 못했었다.

 

당시 완전 탐색으로만 문제를 해결하려 했었는데,

이번에는 여기에 메모리제이션을 적용해 시간을 줄여보았고

결과적으로 4ms의 시간으로 문제를 해결할 수 있었다.

 

문제를 풀면서 까다로웠던 점은,

다음 문자가 될 수 있는 칸은 상하좌우/대각선으로 8개의 칸이 있는데,

이중에서 여러 개의 칸이 다음 문자로 가능할 때 어떤 문자를 선택해야 하느냐였다.

 

나는 단어를 찾을 수 있는 칸을 발견할때까지 가능한 칸을 하나씩 다 시도하게끔 코드를 짰고(완전탐색),

시간을 줄이기 위해 여기에 동적계획법을 적용했다.

단어의 특정 문자를 찾을 때 한번 시도했었지만 실패한 칸은 나중에 다시 시도하지 않도록 메모리제이션 변수를 사용했다.

 

먼저, 2개의 함수를 만들었다.

1. void IsinWord() : 5X5의 게임판을 순회하면서 단어의 첫번째 문자가 있는지 확인하고, 있을 경우 IsFind 함수를 호출해 나머지 문자들도 존재하는지 찾는다. (찾는데 실패했을 경우 바로 종료하지 않고 게임판을 계속 순회하며 첫번째 문자를 다시 찾음)
   

   // 해당되는 단어가 게임판에 존재하는지 확인하는 함수
   void IsinWord() { 
   	for (int x = 0; x < 5; x++) {
   		for (int y = 0; y < 5; y++) {
   			if (word[0] == map[x][y] ){
   				if (IsFind(1, x, y) == 2) {
   					cout << word << " " << "YES" << endl;
   					return;
   				}
   			}
   		}
   	}
   	cout << word << " " << "NO" << endl;
   }​

2. int IsFind(int cur, int x, int y) : 해당 함수를 재귀적으로 호출하며 현재 위치에서 상하좌우/대각선에 다음 문자가 있는지 확인한다.
   

   // 현재 위치에서 상하좌우/대각선에 다음 문자가 있는지 확인하는 함수
   // 반환값 - 0 : 다음문자X, 1 : 다음문자O, 2 : 단어가 게임판에 존재함
   int IsFind(int cur, int x, int y) {
   	int find = 0;
   	
   	// basecase
   	if (word.length() == cur) return 1;		// 단어의 마지막 문자에 도달했을 때
   	if (memory[cur][x][y] == 1) return 0;	// 이미 해당 문자 상하좌우/대각선에는 다음 문자가 없는 것이 확인되었을 때
   
   	// 반복문을 사용해 상하좌우/대각선 확인
   	for (int i = -1; i <= 1; i++) {
   		for (int j = -1; j <= 1; j++) {
   			if ((i == 0 && j == 0) || (x + i < 0) || (x + i > 4) || (y + j < 0) || (y + j > 4)) continue;
   			if (word[cur] == map[x + i][y + j]) {			// 다음 문자가 있을 경우
   				find = IsFind(cur + 1, x + i, y + j);		// 그 다음 문자 확인을 위해 재귀 호출
   
   				// 단어가 게임판에 존재함을 확인했을 때
   				if (find == 1 && cur == word.length() - 1) return 2;	
   				if (find == 2) return 2;								
   			}
   		}
   	}
       	// 해당 위치에서 다음 문자 찾는 것을 실패했을 때
   	if (find == 0) memory[cur][x][y] = 1;
   	return find;
   }

   • int cur : 단어에서 찾는 현재 문자 위치
   • int x, int y : 게임판의 현재 위치
   • basecase
     1. 현재 문자의 위치가 단어의 마지막 위치의 다음 위치에 왔을 때 단어를 찾는 것을 성공한 것이므로 1을 반환하도록 설정.
     2. 해당되는 게임판 위치(x, y)에서 현재 위치의 단어(cur)를 찾는 것을 시도했지만 실패한 경우가 있을 경우 바로 0을 반환하도록 설정(memorization)
   • 함수를 짜면서 시간을 많이 소요했던 부분은,
     현 위치에서 상하좌우/대각선 칸의 문자를 확인하며 다음 문자를 찾을 때, 일치하는 칸이 여러 칸일 수도 있는데 이때 한번 실패하더라도 반복문을 종료시키지 않고 일치하는 다음 칸을 찾도록 만드는 것이었다. 이중반복문에서 재귀호출을 하고 이에 따른 반환값을 0(문자를 찾지 못했을 때), 1(문자를 찾았을 때)로만 설정했기 때문에 이러한 부분을 만드는 것이 까다로웠는데, 여기에 반환값 2(게임판에서 특정 단어를 찾았을 때)를 추가하여 해당 문제를 해결했다. 

 

 

전체 코드

#include <iostream>
#include <string.h>

using namespace std;

char map[5][5];			// board
int memory[10][5][5];	// memorization 
string word;
int N, M;

// 현재 위치에서 상하좌우/대각선에 다음 문자가 있는지 확인하는 함수
// 반환값 - 0 : 다음문자X, 1 : 다음문자O, 2 : 단어가 게임판에 존재함
int IsFind(int cur, int x, int y) {
	int find = 0;
	
	// basecase
	if (word.length() == cur) return 1;		// 단어의 마지막 문자에 도달했을 때
	if (memory[cur][x][y] == 1) return 0;	// 이미 해당 문자 상하좌우/대각선에는 다음 문자가 없는 것이 확인되었을 때

	// 반복문을 사용해 상하좌우/대각선 확인
	for (int i = -1; i <= 1; i++) {
		for (int j = -1; j <= 1; j++) {
			if ((i == 0 && j == 0) || (x + i < 0) || (x + i > 4) || (y + j < 0) || (y + j > 4)) continue;
			if (word[cur] == map[x + i][y + j]) {			// 다음 문자가 있을 경우
				find = IsFind(cur + 1, x + i, y + j);		// 그 다음 문자 확인을 위해 재귀 호출

				// 단어가 게임판에 존재함을 확인했을 때
				if (find == 1 && cur == word.length() - 1) return 2;	
				if (find == 2) return 2;								
			}
		}
	}
    	// 해당 위치에서 다음 문자 찾는 것을 실패했을 때
	if (find == 0) memory[cur][x][y] = 1;
	return find;
}

// 해당되는 단어가 게임판에 존재하는지 확인하는 함수
void IsinWord() { 
	for (int x = 0; x < 5; x++) {
		for (int y = 0; y < 5; y++) {
			if (word[0] == map[x][y] ){
				if (IsFind(1, x, y) == 2) {
					cout << word << " " << "YES" << endl;
					return;
				}
			}
		}
	}
	cout << word << " " << "NO" << endl;
}

int main() {
	cin >> N;
	while (1) {
		for (int i = 0; i < 5; i++) {
			for (int j = 0; j < 5; j++) {
				cin >> map[i][j];
			}
		}
		cin >> M;
		for (int i = 0; i < M; i++) {
			memset(memory, 0, sizeof(memory));
			cin >> word;
			IsinWord();
		}
		if ((--N) == 0) break;
	}
}