[알고리즘] 알고스팟 BOGGLE문제

알고리즘 문제 해결 전략 - BOGGLE 문제

 

재귀 함수 이용

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

using namespace std;

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

char board[5][5];

bool hasWord(int y, int x, const string& word);
bool isRange(int y, int x);

int main() {
	int testcase;
//	char board[5][5];
	string board_sentence;
	int  howmany_word;
	vector<string> words;
	string temp;

	cin>> testcase;
	for (int i = 0; i < testcase; i++) {
		//게임판 생성
		for (int m=0; m < 5; m++) {
			cin>> board_sentence;

			for (int n = 0; n < 5; n++) {
				board[m][n] = board_sentence.at(n);
			}
		}
		cin>>howmany_word;
		// 검사할 단어들 벡터에 삽입
		for (int i = 0; i < howmany_word; i++) {
			cin >> temp;
			words.push_back(temp);
		}
		
		for (vector<string>::iterator itr = words.begin(); itr != words.end(); ++itr) {
			temp = *itr;
			bool check = false; 

			for (int i = 0; i < 5; i++) {
				for (int j = 0; j < 5; j++) {
					if (hasWord(i, j, temp)) {
						check = true;
						break;
					}
				}
			}

			if (check == true) {
				temp += " YES";
			}
			else {
				temp += " NO";
			}
			cout<<temp<<endl;
			
			
		}
	
	}
}

bool hasWord(int y, int x, const string& word) {
	//base case1 : 시작 위치가 범위 밖이면 실패
	if (!isRange(y, x))	return false;
	//base case2 : 첫 글자가 일치하지 않으면 실패
	if (board[y][x] != word[0]) return false;
	// base case3: 단어 길이가 1이면 성공
	if (word.size() == 1) return true;
	//인접한 8칸 검사
	for (int direction=0; direction < 8; direction++) {
		int nextY = y + dy[direction];
		int nextX = x + dx[direction];


		if (hasWord(nextY, nextX, word.substr(1))) {
			return true;
		}
	}
	return false;
}

bool isRange(int y, int x) {
	if (y >= 5) return false;
	else if (y < 5 && y >= 0) {
		if (x >= 5) return false;
		else if (x < 5 && x >= 0) return true;
		else return false;
	}
	else if (y < 0) return false;
}