BOGGLE 질문할께요~!! 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 2using 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 소스 분석은 못하였습니다만, 저는 캐시를 이런 식으로 저장했습니다. 단어를 찾기만 하면 바로 결과를 뱉어내고 종료하면 되므로, 찾은 단어는 캐싱할 필요 없이 해당 위치에서 못 찾은 단어의 리스트만 보관하면 될 것 같습니다. 저는 보드판이 5x5 로 작기 때문에 위치를 따로 키로 저장하지 않고 5x5 캐시를 만들어버렸습니다. 11년 전 link VOCList 1 ABCDE FGHIJ KLMNO PQRST UVWXY 1 KE 위 경우를 생각해보세요. 11년 전 link kwangswei 윽, 열심히 분석하고 있었는데 벌써 리플이 달렸네요 ㅠ.ㅠ 캐싱 관련해서는 문제 정답 받은 후에 꼭 수행속도 빠른 코드를 한 번 보시기 바랍니다. 저도 초보라 무조건 문자열을 다 캐싱해야한다고 생각했었는데 캐싱하는 방법도 가지각색이더라고요~ 11년 전 link kws4679 답변감사합니다. VOCList님이 제시하신 문제를 해결했는데도 오류가 나서 잠시 보류해야할것같네요 ㅠㅠ 답변주셔서 감사합니다 ^^ 11년 전 link 정회원 권한이 있어야 커멘트를 다실 수 있습니다. 정회원이 되시려면 온라인 저지에서 5문제 이상을 푸시고, 가입 후 7일 이상이 지나셔야 합니다. 현재 문제를 푸셨습니다.
kws4679
http://algospot.com/judge/problem/read/BOGGLE
입니다
제가 생각하기에 이 문제는 string을 키로해서
Dynamic Programming을 하는것이라고 생각하는데요
string을 키로 어떻게 캐시에 저장해야하나요??
저는 map< pair < string,int >, int> 처럼 맵으로 저장하였습니다만
답이 제대로 안나오는군요... 어디서 실수했는지 모르겠네요
저렇게 맵으로 캐시를 만든 이유는 특정 위치에 특정단어가 나오는지
검색하기 위함입니다~~
소스 코드도 첨부해봅니다!!
11년 전