알고스팟 - 보글게임(무식하게 풀기방법만 적용)

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

int n, m;
int dx[] = {-1,-1,-1,1,1,1,0,0};
int dy[] = {-1,0,1,-1,0,1,-1,1};
vector <int>visit;
string board[5];


bool findword(const string& s, int x, int y ) {
	//s.substr(1) 로 인해서 재귀를 한번 할때마다 첫번째 글자가 다음 글자로 바뀜
	if (board[x][y] != s[0]) return false;
	if (s.size() == 1) return true;//비교할 글자가 한글자가 되면 탈출
	for (int i = 0;i < 8;i++) {//상하좌우대각선 8방향 검사
		int nextx = x + dx[i];
		int nexty = y + dy[i];
		if (0 <= nextx && nextx < 5 && 0 <= nexty && nexty < 8) {
			if(findword(s.substr(1), nextx, nexty))
			return true;
		}
	}
	return false;
}


int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cin >> n; // 테스트 케이스

	for (int i = 0;i < n;i++) {
		for (int j = 0; j < 5;j++) {
				cin >> board[j];
		}
		int N;
		cin >> N;
		for (int a = 0;a < N;a++) {
			string s;
			cin >> s;
			bool Check = false;

			for (int b = 0;b < 5; b++) {
				for (int c = 0;c < 5; c++) {
					if (board[b][c] == s[0]) //보드판을 돌면서 첫번째 숫자랑 같은거만 일단 시작하기 때문에
					{
						Check = findword(s, b, c);
						if (Check)break;

					}
					if (Check)break;
				}
			}
			if (Check)
				cout << s << " " << "YES\n";
			else
				cout << s << " " << "NO\n";
		}
	}
	

	return 0;
}

 이 문제는 흔하게 완전탐색에서 쓰이는 visit 체크를 하지 않는다. 한번 지나간것도 또 지나갈 수 있기 때문인데 이렇게 가지치기를 하지 않는 문제기 때문에 위의 코드로 자신의 컴퓨터에서 돌리면 돌아가지만 알고스팟에 제출하면 시간이 부족해서 되지 않는다. 

추후에 배울 메모이제이션을 사용하면 시간 초과없이 통과한다고 한다. 

나중에 따로 코드를 작성해서 올리겠다.

문제출처:https://www.algospot.com/judge/problem/read/BOGGLE