저는 재귀가 아닌 방식으로 시도해보았는데요.

일단 주어진 문자열의 글자들이 각각 보드에 어떤 위치에 있는지 0~24로 넘버링하여 각각 벡터에 저장한 다음 (실제로는 한 벡터에 저장하지만 각 글자마다 몇 개가 존재하는 지 저장하는 배열이 존재) 첫 글자열부터 다음 글자가 인접해 있으면 마킹하는 방식으로 마지막 글자 중 마킹된 글자가 하나라도 존재하면 주어진 글자열을 찾았다라고 판단하는 알고리즘을 구현했습니다.

EX) 예제에 주어진 보드에서 GIRL을 찾을 경우
URLPM
XPRET
GIAET
XTNZY
XOQRS

G - 10
I - 11
R - 1 7 23
L - 2

-> 10 - 11 : 포지션 차이가 1이므로 인접 & 마킹
-> 11 - 7 : 포지션 차이가 4이므로 인접 & 마킹 (1 23은 마킹X)
-> 7 - 2 : 포지션 차이가 5이므로 인접 & 마킹
= L그룹에 마킹된 포지션이 있으므로 주어진 문자열 존재

근데 이 방식의 맹점을 아무리 고민해도 찾을 수가 없어서 질문 드립니다. 실제론 떨어져 있지만 포지션 상으로 1,4,5,6 차이가 나는 경우는 (EX : 9-10, 4-10 등) 예외로 걸러내고 있는데도 오답이 나오네요ㅠㅠ

 import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int cases = Integer.parseInt(sc.nextLine()); 

        char[][] board;

        Vector<Letter> L;

        while (cases-- > 0) {
            board = new char[5][5];

            for (int i = 0; i < 5; i++)
                board[i] = sc.nextLine().toCharArray();     // build board

            int num_word = Integer.parseInt(sc.nextLine());

            for (int i = 0; i < num_word; i++) {
                L = new Vector<Letter>();
                char[] word = sc.nextLine().toCharArray();  // scan word
                int[] index = new int[11];                  // letter count array

                boolean isFound = false;
                boolean miss = false;

                int cnt = 0;
                index[0] = 0;
                for(int n=0; n<word.length; n++) {
                    for (int j = 0; j < 5; j++) {
                        for (int k = 0; k < 5; k++) {
                            if(board[j][k] == word[n]) {
                                L.addElement(new Letter(j * 5 + k, n));
                                cnt++;
                            }
                        }
                    }

                    if(index[n] == cnt)
                    {
                        miss = true;
                        break;
                    }

                    index[n+1] = cnt;
                }
                
                // if missing letter exists, then skip the case and print "NO"
                if(miss)
                {
                    System.out.println("NO");
                    continue;
                }

                for(int m=0; m<word.length-1; m++) {
                    for(int n=index[m]; n<index[m+1]; n++) {
                        for(int p=index[m+1]; p<index[m+2]; p++)
                        {
                            if(        (Math.abs(L.elementAt(n).pos - L.elementAt(p).pos) == 1 && L.elementAt(n).pos/5 == L.elementAt(p).pos/5)
                                    || (Math.abs(L.elementAt(n).pos - L.elementAt(p).pos) == 4 && L.elementAt(n).pos/5 != L.elementAt(p).pos/5)
                                    || (Math.abs(L.elementAt(n).pos - L.elementAt(p).pos) == 5 )
                                    || (Math.abs(L.elementAt(n).pos - L.elementAt(p).pos) == 6 && Math.abs(L.elementAt(n).pos/5 - L.elementAt(p).pos/5) == 1))
                            {
                                if(L.elementAt(n).id == 0)
                                    L.elementAt(p).id = L.elementAt(n).id;
                            }
                        }
                    }
                }

                for(int j=index[word.length-1]; j<index[word.length]; j++)
                {
                    if(L.elementAt(j).id == 0)
                    {
                        isFound = true;
                        break;
                    }
                }

                if(isFound)
                    System.out.println("YES");
                else
                    System.out.println("NO");
            }
        }
    }
}

class Letter
{
    int pos;
    int order;
    int id;

    public Letter(int p, int o)
    {
        pos = p;
        order = o;

        if(o == 0)
            id = 0;
        else
            id = -1;
    }
}