cache 배열을 이용하여 재귀탐색중 인접행렬에서
찾을수있는 다음문자가 없다면 탐색할 필요 없도록 하였습니다.
초기화 부분도 신경썻는데 어느부분에서 문제가 발생하였는지 조언 부탁드립니다.
#include<stdio.h>#include<string.h>#include<memory.h>charword[11];charback_g[6][6];intcache[11][6][6];intneighbor_dy[8]={-1,-1,0,1,1,1,0,-1};intneighbor_dx[8]={0,1,1,1,0,-1,-1,-1};intw_lenght=0;intoutput=0;intcheck_word(inty,intx,intword_index){intdx,dy=0;if(word_index==w_lenght)return1;if(cache[word_index][y][x]==0)return0;if(cache[word_index][y][x]==-1)for(inti=0;i<8;i++){dx=x+neighbor_dx[i];dy=y+neighbor_dy[i];if(dx<0||dx>4||dy<0||dy>4)continue;if(back_g[dy][dx]==word[word_index]){cache[word_index][dy][dx]=1;output=check_word(dy,dx,word_index+1);}}if(output==1)return1;else{cache[word_index][y][x]=0;return0;}}intsearch(){output=0;intans=0;for(inti=0;i<5;i++)for(intj=0;j<5;j++){if(back_g[i][j]==word[0])ans=check_word(i,j,1);if(ans==1)return1;}return0;}intmain(){intN=0;// word 개수inti=0;intC=0;intmatching_word=0;scanf("%d",&C);while(C-->0){i=0;while(i<5){scanf("%s",back_g[i]);i++;}scanf("%d",&N);for(i=0;i<N;i++){memset(cache,-1,sizeof(cache));matching_word=0;w_lenght=0;scanf("%s",word);w_lenght=strlen(word);matching_word=search();if(matching_word==1)printf("%s YES\n",word);elseprintf("%s NO\n",word);}}return0;}
JinwooP
BOGGLE
알고리즘 문제해결전략
cache 배열을 이용하여 재귀탐색중 인접행렬에서
찾을수있는 다음문자가 없다면 탐색할 필요 없도록 하였습니다.
초기화 부분도 신경썻는데 어느부분에서 문제가 발생하였는지 조언 부탁드립니다.
8년 전