일단 주어진 문자열의 글자들이 각각 보드에 어떤 위치에 있는지 0~24로 넘버링하여 각각 벡터에 저장한 다음 (실제로는 한 벡터에 저장하지만 각 글자마다 몇 개가 존재하는 지 저장하는 배열이 존재) 첫 글자열부터 다음 글자가 인접해 있으면 마킹하는 방식으로 마지막 글자 중 마킹된 글자가 하나라도 존재하면 주어진 글자열을 찾았다라고 판단하는 알고리즘을 구현했습니다.
EX) 예제에 주어진 보드에서 GIRL을 찾을 경우
URLPM
XPRET
GIAET
XTNZY
XOQRS
G - 10
I - 11
R - 1 7 23
L - 2
-> 10 - 11 : 포지션 차이가 1이므로 인접 & 마킹
-> 11 - 7 : 포지션 차이가 4이므로 인접 & 마킹 (1 23은 마킹X)
-> 7 - 2 : 포지션 차이가 5이므로 인접 & 마킹
= L그룹에 마킹된 포지션이 있으므로 주어진 문자열 존재
근데 이 방식의 맹점을 아무리 고민해도 찾을 수가 없어서 질문 드립니다. 실제론 떨어져 있지만 포지션 상으로 1,4,5,6 차이가 나는 경우는 (EX : 9-10, 4-10 등) 예외로 걸러내고 있는데도 오답이 나오네요ㅠㅠ
importjava.util.*;publicclassMain{publicstaticvoidmain(String[]args){Scannersc=newScanner(System.in);intcases=Integer.parseInt(sc.nextLine());char[][]board;Vector<Letter>L;while(cases-->0){board=newchar[5][5];for(inti=0;i<5;i++)board[i]=sc.nextLine().toCharArray();// build boardintnum_word=Integer.parseInt(sc.nextLine());for(inti=0;i<num_word;i++){L=newVector<Letter>();char[]word=sc.nextLine().toCharArray();// scan wordint[]index=newint[11];// letter count arraybooleanisFound=false;booleanmiss=false;intcnt=0;index[0]=0;for(intn=0;n<word.length;n++){for(intj=0;j<5;j++){for(intk=0;k<5;k++){if(board[j][k]==word[n]){L.addElement(newLetter(j*5+k,n));cnt++;}}}if(index[n]==cnt){miss=true;break;}index[n+1]=cnt;}// if missing letter exists, then skip the case and print "NO"if(miss){System.out.println("NO");continue;}for(intm=0;m<word.length-1;m++){for(intn=index[m];n<index[m+1];n++){for(intp=index[m+1];p<index[m+2];p++){if((Math.abs(L.elementAt(n).pos-L.elementAt(p).pos)==1&&L.elementAt(n).pos/5==L.elementAt(p).pos/5)||(Math.abs(L.elementAt(n).pos-L.elementAt(p).pos)==4&&L.elementAt(n).pos/5!=L.elementAt(p).pos/5)||(Math.abs(L.elementAt(n).pos-L.elementAt(p).pos)==5)||(Math.abs(L.elementAt(n).pos-L.elementAt(p).pos)==6&&Math.abs(L.elementAt(n).pos/5-L.elementAt(p).pos/5)==1)){if(L.elementAt(n).id==0)L.elementAt(p).id=L.elementAt(n).id;}}}}for(intj=index[word.length-1];j<index[word.length];j++){if(L.elementAt(j).id==0){isFound=true;break;}}if(isFound)System.out.println("YES");elseSystem.out.println("NO");}}}}classLetter{intpos;intorder;intid;publicLetter(intp,into){pos=p;order=o;if(o==0)id=0;elseid=-1;}}
용간지
저는 재귀가 아닌 방식으로 시도해보았는데요.
일단 주어진 문자열의 글자들이 각각 보드에 어떤 위치에 있는지 0~24로 넘버링하여 각각 벡터에 저장한 다음 (실제로는 한 벡터에 저장하지만 각 글자마다 몇 개가 존재하는 지 저장하는 배열이 존재) 첫 글자열부터 다음 글자가 인접해 있으면 마킹하는 방식으로 마지막 글자 중 마킹된 글자가 하나라도 존재하면 주어진 글자열을 찾았다라고 판단하는 알고리즘을 구현했습니다.
EX) 예제에 주어진 보드에서 GIRL을 찾을 경우
URLPM
XPRET
GIAET
XTNZY
XOQRS
-> 10 - 11 : 포지션 차이가 1이므로 인접 & 마킹
-> 11 - 7 : 포지션 차이가 4이므로 인접 & 마킹 (1 23은 마킹X)
-> 7 - 2 : 포지션 차이가 5이므로 인접 & 마킹
= L그룹에 마킹된 포지션이 있으므로 주어진 문자열 존재
근데 이 방식의 맹점을 아무리 고민해도 찾을 수가 없어서 질문 드립니다. 실제론 떨어져 있지만 포지션 상으로 1,4,5,6 차이가 나는 경우는 (EX : 9-10, 4-10 등) 예외로 걸러내고 있는데도 오답이 나오네요ㅠㅠ
7년 전