보글 게임(BOGGLE)

https://algospot.com/judge/problem/read/BOGGLE#

처음에 백트래킹 문제인줄 알고, PRETTY 하나만 해봤는데도 시간 초과가 발생했다.

아예 잘못 짠 코드인가보다.

그래서, BFS로 될 것 같아서 해봤더니 한 줄로 이어서 만들 수 없는 경우의 수가 있기 때문에 불가능했다.

분명 재귀함수를 써야하는데, 구현을 잘 못 해서, 다른 분의 코드를 참고하였다.

좀 더 구현에 있어서 공부를 해야겠다.

#include <iostream>
#include <queue>
#include <stack>
#include <cstdio>
#include <vector>
#include <cstring>
#include <string>
#include <math.h>
#include <algorithm>
#include <map>
 
using namespace std;
 
char Map[5][5];
 
char word[11];
 
int dy[8] = { -1, -1, -1, 0, 0, 1, 1, 1 };
int dx[8] = { 0, -1, 1, -1, 1, -1, 1, 0 };
 
bool visit[5][5][11] = { false, };
 
bool bruteforce(int y, int x, int index)
{
    visit[y][x][index] = true; // 방문 기록
 
    if (Map[y][x] != word[index]) return false; // 일치하지 않으면 false
 
    if (index == strlen(word) - 1) return true;
 
    for (int i = 0; i < 8; i++)
    {
        int ny = y + dy[i];
        int nx = x + dx[i];
 
        if (ny < 0 || ny >= 5 || nx < 0 || nx >= 5 || visit[ny][nx][index + 1]) continue;
 
        if (bruteforce(ny, nx, index + 1)) return true;
    }
 
    return false;
}
 
int main(void)
{
    int T = 0;
 
    scanf("%d", &T);
 
    while (T--)
    {
        for (int i = 0; i < 5; i++)
        {
            for (int j = 0; j < 5; j++)
            {
                cin >> Map[i][j];
            }
        }
 
        int N = 0;
 
        scanf("%d", &N);
 
        for (int i = 0; i < N; i++)
        {
            memset(visit, false, sizeof(visit));
 
            scanf("%s", word);
 
            printf("%s ", word);
 
            bool result = false;
 
            for (int h = 0; h < 5; h++)
            {
                for (int w = 0; w < 5; w++)
                {
                    if (bruteforce(h, w, 0))
                    {
                        result = true;
 
                        break;
                    }
                }
 
                if (result) break;
            }
 
            if (result) printf("YES\n");
            else printf("NO\n");
        }
    }
    
    return 0;
}