문제:

hasWord(y, x, word) = 보글 게임판의 (y, x)에서 시작하는 단어 word의 존재 여부를 반환

풀이:

브루트 포스가 일종의 노가다 형식으로 문제를 푸는 방식이면 완전 탐색을 통해 단어를 찾을 때 까지 모든 인접칸을 다 확인하는 것이다.

일단 시작 위치를 정할 수 있기 때문에 그 위치에서 움직일 수 있는 방향은 8방향이 있으니 모든 경우의 수를 미리 만들어 놓고 첫번째 좌표의 x와 y값에 각각 더하면 된다.

기저 사례:

재귀함수를 이용할 것이기 때문에 언제 탐색을 멈춰야 하는지 정해 놓아야 한다:

1. Out of range일 때 - 보드 밖으로 나갔을 때 → return false
2. 제일 첫번째 좌표가 단어랑 맞지 않을 때 → return false
3. (2번의 경우가 아니고) 원하는 단어가 한글자일 때 → return true (2번이랑 3번은 순서 바뀌면 안됨)

🔎간결한 코드를 작성할 때 팁으로 입력이 잘못 되었거나 범위 밖으로 나갈 경우의 기저 사례도 미리 넣는 것(1번의 경우)

코드:

#include <iostream>

using namespace std;

const int dx[8] = {-1, -1, -1, 1, 1, 1, 0, 0};
const int dy[8] = {-1, 0, 1, -1, 0, 1, -1,1};
string dictionary[4] = {"GEEKS", "FOR", "QUIZ", "GO"};
char board[3][3] = {{'G', 'I', 'Z'},
										{'U', 'E', 'K'},
                    {'Q', 'S', 'E'}};
bool inRange(int y, int x){
	if(y >= 0 && y <= 2 && x >= 0 && x <= 2 ) return true;
	return false;
}

bool hasWord(int y, int x, const string& word){
	if(!inRange(y,x)) return false; //out of range
	
	if(board[y][x] != word[0]) return false; //first word wrong
	if(word.size() == 1) return true; //one word and matches
	for(int direction = 0; direction < 8; direction++){
		int nextY = y+dy[direction], nextX = x+dx[direction];
		if(hasWord(nextY, nextX, word.substr(1))){
			return true;
		}
	}
	return false;
}

int main(void){
    cout<< hasWord(0, 0, dictionary[0]) << endl;
}

시간 복잡도: