[ALGOSPOT] BOGGLE_C언어

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

풀이

책에서 풀라는데로 풀었는데...시간초과가 떠서...봤더니 당연히 시간 초과가 날 수 밖에 없다.

내가 계산한바에 따르면..

단어의 최대 길이는10으로 가정하고 주어진 단어가 존재하지 않을경우

맵을 전체 5*5를 다 뒤지며 8가지 경로로 10번 나아간다고 치면 25*8^9가되어 시간초과가 난다.(계산이 틀릴수도 있지만 시간초과가 나는 것은 확실하다.)

풀이는 처음에 main함수에서 주어진 배열 map의 시작점을 다 뒤지도록 이 중 포문을 돌리며

재귀한수에 함수의 위치와 index값을 넘겨준다.

그리고 해당 index값과 map의 문자가 같지 않으면 return 0; 값으면 다음 인자를 찾기 위해 주위의 8방향을 탐색해준다.

그리고 마지막에 단어의 길이와 index값을 비교하여 같다고 판단하면 return 1;을 해주면 된다.

제출한 코드(시간초과 남)

#include <stdio.h>
#include <string.h>
char map[7][7];
char voca[15];
int dx[] = { -1,0,1,1,1,0,-1,-1 };//↖↑↗→↘↓↙←
int dy[] = { -1,-1,-1,0,1,1,1,0 };
int T,t,len;
 
int search(int y,int x, int index)
{
    if (map[y][x] != voca[index])
        return 0;
    
    if (map[y][x]==voca[len - 1]&&index == len - 1)
        return 1;
        
    for (int i = 0; i < 8; i++)
    {
        int xx = x + dx[i];
        int yy = y + dy[i];
 
        if (xx <= 5 && yy <= 5 && 0 < yy && 0 < xx)
        {
            if(search (yy, xx, index + 1))
                return 1;
        }
    }
    return 0;
}
 
 
int main()
{
    scanf("%d",&T);
    getchar();
    while (T--) {
        memset(map, 0, sizeof(map));
 
        for (int i = 1; i <= 5; i++)
        {
            for (int j = 1; j <= 5; j++)
            {
                scanf("%1c", &map[i][j]);
            }
            getchar();
        }
        scanf("%d",&t);
        getchar();
        while (t--)
        {
            int flag = 0;
            memset(voca, 0, sizeof(voca));
            scanf("%s",voca);
            getchar();
            len = strlen(voca);
            for (int i = 1; i <= 5; i++)
            {
                for (int j = 1; j <= 5; j++)
                {
                    flag = search(i, j, 0);
                    if (flag == 1)
                        break;
                }
                if (flag == 1)
                    break;
            }
            if (flag == 1)
                printf("%s YES\n",voca);
            else
                printf("%s NO\n", voca);
        }
    }
    return 0;
}