BOGGLE 문제 관련 질문드립니다.

  • MIS
    MIS


    안녕하세요. 현재 알고리즘 문제 해결 전략 책으로 공부 중인 학생입니다.
    6장의 무식하게 풀기의 1번 문제인 BOGGLE관련 문제를 풀던 중 계속 오답이 나와서 질문드립니다.
    저의 코드와 책의 코드를 비교했지만 크게 다른 점이 없다고 생각되어서 더욱 의문이 생깁니다.
    예제와 답이 같게 나오며, 댓글에 있는 다른 예제들도 모두 맞게 나옵니다.
    그 외의 추가 예제들을 만들어서 넣어봤지만, 예상 결과와 맞게 나옵니다.
    그래서인지 어느 부분이 틀렸는지 감이 더욱이 안잡힙니다.
    코드 부분에서 틀린 부분과 더 나은 방향의 코드에 대한 조언을 듣고 싶습니다.
    저의 코드는 아래와 같습니다.
    감사합니다.

    #include<iostream>
    #include<string>
    #include<string.h>
    
    #define MAX_VOCA_CASE 10
    #define MAX_VOCA_LENGTH 10
    #define MAP_SIZE 5
    #define STEP_AROUND 8
    
    using namespace std;
    
    int N, C; // test case, vocabulary
    char Map[MAP_SIZE][MAP_SIZE];
    string Voca[MAX_VOCA_CASE];
    int Cache[MAP_SIZE][MAP_SIZE][MAX_VOCA_LENGTH];
    const int Dx[STEP_AROUND] = {-1, -1, -1, 0, 0, 1, 1, 1};
    const int Dy[STEP_AROUND] = {-1, 0, 1, -1, 1, -1, 0, 1};
    
    bool is_beyond_boundary(int x, int y)
    {
        if (x < 0 || MAP_SIZE <= x) return true;
        else if (y < 0 || MAP_SIZE <= y) return true;
        else return false;
    }
    
    int boggle(int voca, int x, int y, int cur)
    {
        if (is_beyond_boundary(x, y)) return 0;
    
        // 1. 경계선 검사
        // 2. cache 검사
        // 3. 모든 문자를 체크했는지 확인
        // 4. 올바른 위치의 문자가 왔는지 확인
        // 5. 주변 확인
        // 6. 주변을 확인한 결과 반환
        int &res = Cache[x][y][cur];
    
        if (res != -1) return res;
        else if (cur == Voca[voca].length()) return res = 1;
        else if (Map[x][y] != Voca[voca][cur]) return res = 0;
        else
        {
            for (int step = 0; step < STEP_AROUND; ++step)
            {
                res = boggle(voca, x + Dx[step], y + Dy[step], cur + 1);
    
                if (res == 1) break;
            }
        }
    
        return res;
    }
    
    int main(void)
    {
        ios::sync_with_stdio(false);
        freopen("input.txt", "r", stdin);
    
    
    
        //input
        scanf("%d", &N);
    
        while (N--)
        {
            for (int line = 0; line < MAP_SIZE; ++line)
            {
                for (int cur_width = 0; cur_width < MAP_SIZE; ++cur_width)
                {
                    char c;
                    while ((c = getchar()) == '\n' || c == '\0') {}
                    Map[line][cur_width] = c;
                }
            }
    
    
            scanf("%d", &C);
            for (int cur_voca = 0; cur_voca < C; ++cur_voca)
            {
                cin >> Voca[cur_voca];
            }
    
    
    
            //processing
            for (int voca = 0; voca < C; ++voca)
            {
                bool done = false;
                memset(Cache, -1, sizeof(Cache));
    
                // 0. 문자열의 처음이 맞는지 확인함.
                for (int line = 0; line < MAP_SIZE && !done; ++line)
                {
                    for (int cur = 0; cur < MAP_SIZE && !done; ++cur)
                    {
                        if (Voca[voca][0] == Map[line][cur])
                        {
                            done = boggle(voca, line, cur, 0);
                        }
                    }
                }
    
    
                // output
                cout << Voca[voca] << " " << ((done) ? "YES" : "NO") << endl;
            }
    
        }
    
    
        return 0;
    }
    

    7년 전
4개의 댓글이 있습니다.
  • Corea
    Corea

    scanf와 cin을 섞어 쓰시면 안됩니다. 둘 중 하나만 사용해주세요.


    7년 전 link
  • Corea
    Corea

    그리고 freopen 구문은 제거해주셔야겠죠!


    7년 전 link
  • wookayin
    wookayin

    scanf, cin을 섞어쓰면 안되는건 참고로 ios::sync_with_stdio(false); 를 썼을때 이야기입니다 :)


    7년 전 link
  • MIS
    MIS

    헉.. 그렇군요.. 감사합니다! 해결됐습니다.


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