BOGGLE 문제 오답이 도대체 무엇일까요... ㅠㅠ 답변부탁드립니다.

  • kimsubong
    kimsubong

    재귀 호출에 메모이제이션을 이용해서 풀었는데요,
    왠만한 예시를 다 해봐도 오답을 못찾겠어요 ㅠㅠ
    어디서 오답이 나오는 걸까요?
    답변 부탁드립니다!

    #include <stdio.h>
    #include <stdlib.h>
    #include <string.h>
    int cache[7][7];    //메모이제이션 캐쉬
    int dx[8] = {-1,-1,-1, 0, 0, 1, 1, 1};
    int dy[8] = {-1, 0, 1,-1, 1,-1, 0, 1};
    int arr[7][7];      //5x5 보글판 테두리를 0으로 씌우기 위해 7x7
    char **word;
    int result;
    int find(int, int, char *);
    int substr(char *word, int len)
    {   //c++ substr 구현
        int i;
        if(strlen(word) < len) return 0;
        for(i = 0; i < strlen(word) - len ; i++)
        {
            word[i] = word[i + len];
        }
        word[i] = '\0';
        return 1;
    }
    int main()
    {
        int i,j,testCase;
        int num; // 찾을 단어 수
        int tCase; // 케이스 수
        memset(cache,-1,sizeof(cache));
        //freopen("input.txt","r",stdin);
        scanf("%d",&testCase);
        while(getchar() != '\n');
        for(tCase = 0; tCase < testCase; tCase++)
        {
            for(i = 1; i < 6; i++)
            {
                for(j = 1; j < 6; j++)
                {
                    scanf("%c",&arr[i][j]);
                }
                getchar();
            }
            scanf("%d",&num);
            word = (char **)calloc(num,sizeof(char *));
            for(i = 0; i < num; i++)
            {
                word[i] = (char *)calloc(11,sizeof(char));
            }
            for(i = 0; i < num; i++)
            {
                scanf("%s",word[i]);
                printf("%s ",word[i]);
                for(j = 1; j <= 5; j++)
                {
                    for(int k = 1; k <= 5; k++)
                    {
                        memset(cache,-1,sizeof(cache));
                        if(find(j,k,word[i]) == 1)
                        {   //한 좌표에서 단어의 유무 확인
                            result = 1;
                            break;
                        }
                    }
                    if(result == 1)
                    {
                        break;
                    }
                }
                if(result == 1)
                {
                    printf("YES\n");
                }
                else
                {
                    printf("NO\n");
                }
    
                result = 0;
                getchar();
            }
            for(i = 0; i < num; i++)
            {
                free(word[i]);
            }
            free(word);
        }
    
        return 0;
    }
    int find(int x, int y, char* w)
    {
        int i;
        char word[11];
        strcpy(word,w);
        if(arr[x][y] == 0)
        {
            return 0;
        }
        if(arr[x][y] != word[0])
        {
            return 0;
        }
        if(strlen(word) == 1)
        {
            return 1;
        }
        int* ret = &cache[x][y];
        if(*ret != -1)
        {
            return *ret;
        }
        substr(word,1);
        for(i = 0; i < 8; i++)
        {
            int nextX = x + dx[i];
            int nextY = y + dy[i];
            if(find(nextX,nextY,word) == 1)
            {
                return *ret = 1;
            }
        }
    
        return *ret = 0;
    }
    

    8년 전
2개의 댓글이 있습니다.
  • hyunhwan
    hyunhwan

    메모이제이션을 할 때 현재 탐색하는 위치의 정보만 가지고는 부족할 것 같은데요. 길이 역시 고려가 되야 메모이제이션이 제대로 동작할 것 같습니다. 다시 말해서 탐색 위치만 가지고는 cache에 저장된 결과가 어떤 문자열에 대해 1을 반환했는지 알 수 없어 보입니다.

    그리고 추가적으로 strlen을 자주 쓰시면 소스코드의 동작시간이 느려질 수 있으니 주의하시길 바랍니다. 다음의 커멘트 참고해주세요: https://algospot.com/forum/read/1981/#c9680


    8년 전 link
  • kimsubong
    kimsubong

    감사합니다!! 덕분에 고쳐서 맞췄어요~

    뭔가 2프로 부족하다고 생각했는데 메모이제이션을 이제야

    이해하게 되었습니다. 다시한번 감사합니다


    8년 전 link
  • 정회원 권한이 있어야 커멘트를 다실 수 있습니다. 정회원이 되시려면 온라인 저지에서 5문제 이상을 푸시고, 가입 후 7일 이상이 지나셔야 합니다. 현재 문제를 푸셨습니다.