BOGGLE 질문할께요~!!

  • kws4679
    kws4679

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

    입니다

    제가 생각하기에 이 문제는 string을 키로해서

    Dynamic Programming을 하는것이라고 생각하는데요

    string을 키로 어떻게 캐시에 저장해야하나요??

    저는 map< pair < string,int >, int> 처럼 맵으로 저장하였습니다만

    답이 제대로 안나오는군요... 어디서 실수했는지 모르겠네요

    저렇게 맵으로 캐시를 만든 이유는 특정 위치에 특정단어가 나오는지

    검색하기 위함입니다~~

    소스 코드도 첨부해봅니다!!

    #include <iostream>
    #include <vector>
    #include <string>
    #include <map>

    #define TRUE 3
    #define FALSE 2

    using namespace std;
    char board[25];
    vector<string> words;
    map<pair<string,int>, int> cache;

    int isPossible(string word, int n, int k){
    if(!word.size()) return TRUE;
    map<pair<string,int>,int>::iterator it = cache.find(pair<string,int>(word,k));
    int ret = it->second;
    if(it != cache.end() && (ret == TRUE || ret == FALSE)) return ret;
    vector<int> way;
    if(!n){
    for(int i = 0; i < 25; i++) if(word[0] == board[i]) way.push_back(i);
    } else {
    for(int i = k-6; i < k-3; i++)
    for(int j = i; j <= i + 10; j = j + 5)
    if(j != k && j > 0 && j < 25) way.push_back(j);
    }
    for(int i = 0; i < way.size(); i++)
    if((word[0] == board[way[i]]) && (isPossible(word.substr(1, word.size()), n+1, way[i]) == TRUE)){
    ret = TRUE;
    cache.insert(pair<pair<string,int>, int>(pair<string,int>(word,k+1), ret));
    return ret;
    }
    ret = FALSE;
    cache.insert(pair<pair<string,int>, int>(pair<string,int>(word,k+1), ret));
    return ret;
    }

    const char* boggle(string word){
    if(isPossible(word, 0, 0) == TRUE) return "YES";
    else return "NO";
    }

    int main(){
    int c;
    scanf("%d", &c);
    while(c--){
    for(int i = 0; i < 5; i++)
    scanf("%s", &board[i*5]);
    int n;
    scanf("%d", &n);
    words = vector<string> ();
    while(n--){
    string word;
    cin >> word;
    words.push_back(word);
    }
    for(int i = 0; i < words.size(); i++) cout << words[i] << " " << boggle(words[i]) << endl;
    }
    return 0;
    }


    11년 전
4개의 댓글이 있습니다.
  • kwangswei
    kwangswei

    소스 분석은 못하였습니다만, 저는 캐시를 이런 식으로 저장했습니다.

    1. 단어를 찾기만 하면 바로 결과를 뱉어내고 종료하면 되므로, 찾은 단어는 캐싱할 필요 없이 해당 위치에서 못 찾은 단어의 리스트만 보관하면 될 것 같습니다.
    2. 저는 보드판이 5x5 로 작기 때문에 위치를 따로 키로 저장하지 않고 5x5 캐시를 만들어버렸습니다.


    11년 전 link
  • VOCList
    VOCList

    1
    ABCDE
    FGHIJ
    KLMNO
    PQRST
    UVWXY
    1
    KE

    위 경우를 생각해보세요.


    11년 전 link
  • kwangswei
    kwangswei

    윽, 열심히 분석하고 있었는데 벌써 리플이 달렸네요 ㅠ.ㅠ

    캐싱 관련해서는 문제 정답 받은 후에 꼭 수행속도 빠른 코드를 한 번 보시기 바랍니다. 저도 초보라 무조건 문자열을 다 캐싱해야한다고 생각했었는데 캐싱하는 방법도 가지각색이더라고요~


    11년 전 link
  • kws4679
    kws4679

    답변감사합니다. VOCList님이 제시하신 문제를 해결했는데도 오류가 나서 잠시 보류해야할것같네요 ㅠㅠ

    답변주셔서 감사합니다 ^^


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