보글 문제에서 메모이제이션 관련하여 질문하겠습니다.

  • skghtjr2
    skghtjr2

    책 보면서 공부하고 있는 초보자 입니다.
    보글 문제를 풀어보고 있었는데요.
    사용 언어는 자바입니다.
    책에 있는 알고리즘대로 작성하여 예시 입력 출력 값은 출력하였습니다.
    여기서 8장에 있는 메모이제이션을 적용하여 시간 초과를 해결하려고 했습니다.
    메모이제이션을 사용하는 이유가 계산 값을 저장하여 중복되는 계산을 피하는 것인데
    이 보글 문제에서 어떻게 적용해야할지 잘 모르겠습니다.
    제가 시도한 방법은
    boolean Cashe[][][] 배열을 생성하여 첫번째 두번째 인자는 5*5 board판이고
    마지막 인자는 PRETTY 단어의 갯수를 지정하여 검색하는 알파벳의 True False 값을 메모이제이션 하였습니다.
    그런데 이렇게 메모이제이션 한 값을 활용하여 중복되는 계산이 많이 줄어들지 않는거 같습니다.
    혼자 생각을 해봤는데 초보자라 그런지 해결을 못하고 있습니다 ㅠ
    제가 메모이제이션 지정하는게 잘못된 것인가요? 도움 부탁드리겠습니다.
    아래는 제가 작성한 코드입니다.

    import java.util.Scanner;

    public class Boggle {

    static char [][] board = new char [5][5];
    static boolean [][][] cashe;
    static int [] dx = { -1, -1, -1, 1, 1, 1, 0, 0};
    static int [] dy = { -1, 0, 1, -1, 0, 1, -1, 1};
    
    
    
    public static void main(String[] args) {
        int T;
        int test_case;
    
    
        Scanner sc = new Scanner(System.in);
    
        T = sc.nextInt();
        sc.nextLine();
        for(test_case = 1; test_case <= T; test_case++) {
            //  이 부분에서 알고리즘 프로그램을 작성하십시오.
    
    
            for(int i = 0; i < 5; i++){
                String tmp = sc.nextLine();
                for(int j = 0; j <5; j++)
                    board[i][j] = tmp.charAt(j);
            }
    
    
            int number_word = sc.nextInt();
            sc.nextLine();
            String [] word = new String[number_word];
            for(int i = 0; i < number_word; i++)
                word[i] = sc.nextLine();
            boolean res = false;
    
            for(int k = 0; k < number_word; k++){
                cashe = new boolean [5][5][word[k].length()];
                initCashe(word[k].length());
                for(int i = 0; i < 5; i++)
                    for(int j = 0; j < 5; j++){                 
                        if(res = hasWord(i, j, word[k])) {
                            i=5;
                            j=5;
                        }
                    }
                if(res == true) System.out.println(word[k] + " YES");
                else System.out.println(word[k] + " NO");   
            }               
    
    
        }
    }
    
    static boolean isRange(int y, int x){
        if(y <0 || x < 0 || y > 4 || x > 4) return false;
        else return true;
    }
    
    static boolean hasWord(int y, int x, String word){
    
        if(! isRange(y,x) ) return false;
    
        if(!cashe[y][x][word.length()-1]) return false;
    
        if( board[y][x] != word.charAt(0)) return cashe[y][x][word.length()-1]=false;
        if( word.length() == 1) return true;
    
        for(int direction = 0; direction < 8; ++direction){
            int nextY = y + dy[direction], nextX = x + dx[direction];
    
            if( hasWord(nextY, nextX, word.substring(1)) ) return true;
        }
    
    
        return false;       
    
    }
    
    static void initCashe(int n){
        for(int i = 0; i < 5; i++)
            for(int j = 0; j < 5; j++)
                for(int k = 0; k < n; k++)
                    cashe[i][j][k] = true;
    }

    }


    4년 전
1개의 댓글이 있습니다.
  • 정인석
    정인석

    initcashe 캐시 리셋하는걸 memset으로 해보세요~!


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