안녕하세요. 현재 알고리즘 문제 해결 전략 책으로 공부 중인 학생입니다.
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 8usingnamespacestd;intN,C;// test case, vocabularycharMap[MAP_SIZE][MAP_SIZE];stringVoca[MAX_VOCA_CASE];intCache[MAP_SIZE][MAP_SIZE][MAX_VOCA_LENGTH];constintDx[STEP_AROUND]={-1,-1,-1,0,0,1,1,1};constintDy[STEP_AROUND]={-1,0,1,-1,1,-1,0,1};boolis_beyond_boundary(intx,inty){if(x<0||MAP_SIZE<=x)returntrue;elseif(y<0||MAP_SIZE<=y)returntrue;elsereturnfalse;}intboggle(intvoca,intx,inty,intcur){if(is_beyond_boundary(x,y))return0;// 1. 경계선 검사// 2. cache 검사// 3. 모든 문자를 체크했는지 확인// 4. 올바른 위치의 문자가 왔는지 확인// 5. 주변 확인// 6. 주변을 확인한 결과 반환int&res=Cache[x][y][cur];if(res!=-1)returnres;elseif(cur==Voca[voca].length())returnres=1;elseif(Map[x][y]!=Voca[voca][cur])returnres=0;else{for(intstep=0;step<STEP_AROUND;++step){res=boggle(voca,x+Dx[step],y+Dy[step],cur+1);if(res==1)break;}}returnres;}intmain(void){ios::sync_with_stdio(false);freopen("input.txt","r",stdin);//inputscanf("%d",&N);while(N--){for(intline=0;line<MAP_SIZE;++line){for(intcur_width=0;cur_width<MAP_SIZE;++cur_width){charc;while((c=getchar())=='\n'||c=='\0'){}Map[line][cur_width]=c;}}scanf("%d",&C);for(intcur_voca=0;cur_voca<C;++cur_voca){cin>>Voca[cur_voca];}//processingfor(intvoca=0;voca<C;++voca){booldone=false;memset(Cache,-1,sizeof(Cache));// 0. 문자열의 처음이 맞는지 확인함.for(intline=0;line<MAP_SIZE&&!done;++line){for(intcur=0;cur<MAP_SIZE&&!done;++cur){if(Voca[voca][0]==Map[line][cur]){done=boggle(voca,line,cur,0);}}}// outputcout<<Voca[voca]<<" "<<((done)?"YES":"NO")<<endl;}}return0;}
MIS
안녕하세요. 현재 알고리즘 문제 해결 전략 책으로 공부 중인 학생입니다.
6장의 무식하게 풀기의 1번 문제인 BOGGLE관련 문제를 풀던 중 계속 오답이 나와서 질문드립니다.
저의 코드와 책의 코드를 비교했지만 크게 다른 점이 없다고 생각되어서 더욱 의문이 생깁니다.
예제와 답이 같게 나오며, 댓글에 있는 다른 예제들도 모두 맞게 나옵니다.
그 외의 추가 예제들을 만들어서 넣어봤지만, 예상 결과와 맞게 나옵니다.
그래서인지 어느 부분이 틀렸는지 감이 더욱이 안잡힙니다.
코드 부분에서 틀린 부분과 더 나은 방향의 코드에 대한 조언을 듣고 싶습니다.
저의 코드는 아래와 같습니다.
감사합니다.
7년 전