BOGGLE 문제 질문드립니다

  • 용간지
    용간지

    저는 재귀가 아닌 방식으로 시도해보았는데요.

    일단 주어진 문자열의 글자들이 각각 보드에 어떤 위치에 있는지 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 등) 예외로 걸러내고 있는데도 오답이 나오네요ㅠㅠ

     import java.util.*;
    
    public class Main {
        public static void main(String[] args) {
            Scanner sc = new Scanner(System.in);
            int cases = Integer.parseInt(sc.nextLine()); 
    
            char[][] board;
    
            Vector<Letter> L;
    
            while (cases-- > 0) {
                board = new char[5][5];
    
                for (int i = 0; i < 5; i++)
                    board[i] = sc.nextLine().toCharArray();     // build board
    
                int num_word = Integer.parseInt(sc.nextLine());
    
                for (int i = 0; i < num_word; i++) {
                    L = new Vector<Letter>();
                    char[] word = sc.nextLine().toCharArray();  // scan word
                    int[] index = new int[11];                  // letter count array
    
                    boolean isFound = false;
                    boolean miss = false;
    
                    int cnt = 0;
                    index[0] = 0;
                    for(int n=0; n<word.length; n++) {
                        for (int j = 0; j < 5; j++) {
                            for (int k = 0; k < 5; k++) {
                                if(board[j][k] == word[n]) {
                                    L.addElement(new Letter(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(int m=0; m<word.length-1; m++) {
                        for(int n=index[m]; n<index[m+1]; n++) {
                            for(int p=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(int j=index[word.length-1]; j<index[word.length]; j++)
                    {
                        if(L.elementAt(j).id == 0)
                        {
                            isFound = true;
                            break;
                        }
                    }
    
                    if(isFound)
                        System.out.println("YES");
                    else
                        System.out.println("NO");
                }
            }
        }
    }
    
    class Letter
    {
        int pos;
        int order;
        int id;
    
        public Letter(int p, int o)
        {
            pos = p;
            order = o;
    
            if(o == 0)
                id = 0;
            else
                id = -1;
        }
    }
    

    1년 전
2개의 댓글이 있습니다.
  • Corea
    Corea

    출력 형식을 확인해보셨나요?


    1년 전 link
  • 용간지
    용간지

    아,.... 자괴감이 드네요 ㅠㅠ 감사합니다


    1년 전 link
  • 댓글을 남기시려면 로그인하세요.