BOGGLE 동적계획법 오답

  • suri
    suri

    BOGGLE게임 만들었는데 제출하면 오답이라고 나옵니다
    제 머리로는 한계라서 질문드립니다

    일단 게임 board판과 같은 크기의 check배열을 만들어서
    해당지점에서 단어가 만들어질수 없는 경우는 -1로 만들고 단어를 만들때 참고하도록 만들었습니다
    반대로 단어가 모두 만들어지면 거기서 바로 true들을 연달아 return하게 만들었습니다

    import java.io.BufferedReader;
    import java.io.BufferedWriter;
    import java.io.IOException;
    import java.io.InputStreamReader;
    import java.io.OutputStreamWriter;
    import java.util.Arrays;
    
    public class Main {
        static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        static final int size = 5;
        static char[][] board = new char[size][size];
        static int[][] check = new int[size][size];
        static char[] word;
    
        public static void main(String[] args) throws NumberFormatException, IOException {
            int C = Integer.parseInt(br.readLine().trim());
    
            while(C-- > 0) {
                for(int i = 0; i < size; i++) 
                    board[i] = br.readLine().trim().toCharArray();
    
                int N = Integer.parseInt(br.readLine().trim());
    
                while(N-- > 0) {
                    word = br.readLine().trim().toCharArray();
    
                    if(findWord(0, 0, 0))
                        bw.write(String.valueOf(word) + " YES\n");
                    else bw.write(String.valueOf(word) + " NO\n");
    
                    for(int i = 0; i < size; i++)
                        Arrays.fill(check[i], 0);
                }
            }
    
            br.close(); bw.close();
        }
    
        static boolean findWord(int index, int i, int j) {
            if(index == word.length) return true;
    
            if(index == 0) {
                for(int ti = i; ti < size; ti++) {
                    for(int tj = j; tj < size; tj++) {
                        if(board[ti][tj] == word[index] && findWord(index + 1, ti, tj)) return true;
                    }
                }
            } else {
                for(int ti = i - 1; ti <= i + 1; ti++) {
                    for(int tj = j - 1; tj <= j + 1; tj++) {
                        if((ti == i && tj == j) || ti < 0 || ti >= size || tj < 0 || tj >= size) continue;
    
                        if(check[i][j] != -1 && board[ti][tj] == word[index] && findWord(index + 1, ti, tj)) return true;
                    }
                }
            }
    
            check[i][j] = -1;
            return false;
        }
    
    }
    

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