BOGGLE game 질문있습니다!

  • danwoo21
    danwoo21

    BOGGLE
    보글게임 memoization 으로 풀었는데 오답이 뜹니다.
    memoization 방법은 다음과 같습니다.

    현재 5X5 보드에서 찾으려고 하는 단어를 word라고 하면,
    word의 n번째 character와 매칭된 보드의 (i,j) 좌표에서 find메소드를 이용해 모든 경우를 조사한 결과 그 칸은 n번째에 들어오면 안되는 칸이라면 memo[i][j][n]를 false로 만듭니다.

    테스트해본 결과 NO를 YES로 출력하는 경우가 있는것 같은데 구체적인 케이스를 못찾겠습니다. 도움주시면 감사하겠습니다!

    import java.io.File;
import java.io.FileNotFoundException;
import java.io.PrintWriter;
import java.util.Random;
import java.util.Scanner;

public class Main {
    private static final int[] di = { -1, -1, 0, 1, 1, 1, 0, -1 };
    private static final int[] dj = { 0, 1, 1, 1, 0, -1, -1, -1 };
    private static boolean[][][] memo;
    private static char board[][] = new char[5][5];

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int cases = in.nextInt();
        String word;
        for (int c = 0; c < cases; c++) {
            // input board
            for (int i = 0; i < 5; i++)
                board[i] = in.next().toCharArray();

            int N = in.nextInt(); // number of words to find
            for (int i = 0; i < N; i++) {
                word = in.next();

                memo = new boolean[5][5][word.length()];
                initMemo(word.length());
                boolean found = false;
                lp: for (int j = 0; j < 5; j++) {
                    for (int k = 0; k < 5; k++) {
                        if (found = find(word, 0, j, k)) {
                            break lp;
                        }
                    }
                }
                if (found)
                    System.out.println("YES");
                if (!found) {
                    System.out.println("NO");
                }
            }
        }
    }

    public static boolean find(String word, int n, int i, int j) {
        if (n == word.length())
            return true;
        if (i < 0 || i > 4 || j < 0 || j > 4) {
            return false;
        }
        if (!memo[i][j][n])
            return false;
        if (word.charAt(n) != board[i][j]) {
            return false;
        }
        for (int d = 0; d < 8; d++) {
            if (find(word, n + 1, i + di[d], j + dj[d]))
                return true;
        }
        return memo[i][j][n] = false;
    }

    public static void initMemo(int n) {
        for (int i = 0; i < 5; i++)
            for (int j = 0; j < 5; j++)
                for (int k = 0; k < n; k++)
                    memo[i][j][k] = true;
    }
}

    9년 전
0개의 댓글이 있습니다.

  • 정회원 권한이 있어야 커멘트를 다실 수 있습니다. 정회원이 되시려면 온라인 저지에서 5문제 이상을 푸시고, 가입 후 7일 이상이 지나셔야 합니다. 현재 문제를 푸셨습니다.