보글 게임 (ID : BOGGLE)

https://www.algospot.com/judge/problem/read/BOGGLE

algospot.com :: BOGGLE

 

 

1. 첫 번째 시도

 

재귀를 이용하여 완전탐색방법으로 문제를 풀려고 시도했지만 '시간초과' 가 발생하여 통과하지 못했다. 문제 조건중에 지나간 글자를 다시 지나갈 수 있다는 조건 때문에 visited[][] 배열로 방문 체크를 하지못한 점 때문에 수행시간이 오래걸리지 않았나 싶다. 해당 조건을 해결하면서 수행시간도 줄일 수 있는 방법을 찾아봐야겠다. 고민을 해보다가 너무 오래걸린다 싶으면 정답을 봐야겠다.

import java.util.*;

public class Main {

    private static Scanner scanner;
    private static char[][] pan;
    private static String[] targetWords;
    private static int targetWordCount;
    private static int targetWordsOrder;
    private static int[] drow = {-1, -1, 0, 1, 1, 1, 0, -1};
    private static int[] dcol = {0, 1, 1, 1, 0, -1, -1, -1};

    public static void main(String[] args) {
        scanner = new Scanner(System.in);

        int caseCount = Integer.parseInt(scanner.nextLine());
        for (int c = 0; c < caseCount; c++) {
            // 초기화
            pan = new char[5][5];
            targetWords = new String[10];
            List<Map<String, String>> answers = new ArrayList<>();

            // 테스트 데이터 입력
            for (int row = 0; row < 5; row++) {
                String panRow = scanner.nextLine();
                for(int col = 0; col < 5; col++) {
                    pan[row][col] = panRow.charAt(col);
                }
            }

            targetWordCount = Integer.parseInt(scanner.nextLine());

            for (int i = 0; i < targetWordCount; i++) {
                String searchWord = scanner.nextLine();
                targetWords[i] = searchWord;
            }

            // 단어 찾기
            for(int i = 0; i < targetWordCount; i++) {
                targetWordsOrder = i;
                boolean isSearched = searchWord();

                Map<String, String> answer = new HashMap<>();
                answer.put("work", targetWords[targetWordsOrder]);
                answer.put("result", isSearched ? "YES" : "NO");
                answers.add(answer);
            }

            // 결과 출력
            for (Map<String, String> answer : answers) {
                System.out.println(answer.get("work") + " " + answer.get("result"));
            }
        }
    }

    private static boolean searchWord() {
        boolean isSearched = false;
        for(int row = 0; row < 5; row++) {
            for(int col = 0; col < 5; col++) {
                isSearched = recursiveSearchWord(row, col, "", 0);
                if(isSearched) {
                    return true;
                }
            }
        }
        return isSearched;
    }

    private static boolean recursiveSearchWord(int row, int col, String combinedWord, int combinedWordIdx) {
        // 기저 사례 1
        if (targetWords[targetWordsOrder].length() < combinedWordIdx)
            return false;

        if (pan[row][col] == targetWords[targetWordsOrder].charAt(combinedWordIdx)) {
            combinedWord += pan[row][col];

            // 기저 사례 2
            if (targetWords[targetWordsOrder].equals(combinedWord))
                return true;

            for (int i = 0; i < 8; i++) {
                int nextRow = row + drow[i];
                int nextCol = col + dcol[i];

                if (nextRow >= 0 && nextRow < 5 && nextCol >= 0 && nextCol < 5) {
                    boolean isSearched = recursiveSearchWord(nextRow, nextCol, combinedWord, combinedWordIdx + 1);
                    if (isSearched)
                        return true;
                }
            }
        }

        return false;
    }
}

 

 

2. 두 번째 시도

 

수행시간을 줄이기 위해 판 위의 문자 사용여부를 체크하는 isOccupied[][] 배열을 추가했습니다. 그리고 재귀 진행 조건문에서 다음 재귀 함수에서 방문하는 지점의 문자가 타겟 문자열의 다음에 올 문자와 동일한 경우에는 탐색을 진행하도록 소스를 수정해봤지만 이번에도 동일하게 '시간초과'로 통과하지 못했습니다. 시간을 획기적으로 줄일 수 있는 확실한 방법이 필요할 것 같습니다.

import java.util.*;

public class Main {
    private static Scanner scanner;
    private static char[][] pan;
    private static boolean[][] isOccupied;
    private static String[] targetWords;
    private static int targetWordCount;
    private static int targetWordsOrder;
    private static int[] drow = {-1, -1, 0, 1, 1, 1, 0, -1};
    private static int[] dcol = {0, 1, 1, 1, 0, -1, -1, -1};

    public static void main(String[] args) {
        scanner = new Scanner(System.in);

        int caseCount = Integer.parseInt(scanner.nextLine());
        for (int c = 0; c < caseCount; c++) {
            pan = new char[5][5];
            isOccupied = new boolean[5][5];
            targetWords = new String[10];
            List<Map<String, String>> answers = new ArrayList<>();

            for (int row = 0; row < 5; row++) {
                String panRow = scanner.nextLine();
                for(int col = 0; col < 5; col++) {
                    pan[row][col] = panRow.charAt(col);
                }
            }

            targetWordCount = Integer.parseInt(scanner.nextLine());

            for (int i = 0; i < targetWordCount; i++) {
                String searchWord = scanner.nextLine();
                targetWords[i] = searchWord;
            }

            for(int i = 0; i < targetWordCount; i++) {
                initIsOccupied();
                targetWordsOrder = i;
                boolean isSearched = searchWord();

                Map<String, String> answer = new HashMap<>();
                answer.put("work", targetWords[targetWordsOrder]);
                answer.put("result", isSearched ? "YES" : "NO");
                answers.add(answer);
            }

            for (Map<String, String> answer : answers) {
                System.out.println(answer.get("work") + " " + answer.get("result"));
            }
        }
    }

    private static void initIsOccupied() {
        for(int row = 0; row < 5; row++) {
            for(int col = 0; col < 5; col++) {
                isOccupied[row][col] = false;
            }
        }
    }

    private static boolean searchWord() {
        boolean isSearched = false;
        for(int row = 0; row < 5; row++) {
            for(int col = 0; col < 5; col++) {
                isSearched = recursiveSearchWord(row, col, "", 0);
                if(isSearched) {
                    return true;
                }
            }
        }
        return isSearched;
    }

    private static boolean recursiveSearchWord(int row, int col, String combinedWord, int combinedWordIdx) {
        if (targetWords[targetWordsOrder].length() < combinedWordIdx)
            return false;

        if (pan[row][col] == targetWords[targetWordsOrder].charAt(combinedWordIdx)) {
            combinedWord += pan[row][col];
            isOccupied[row][col] = true;

            if (targetWords[targetWordsOrder].equals(combinedWord))
                return true;

            for (int i = 0; i < 8; i++) {
                int nextRow = row + drow[i];
                int nextCol = col + dcol[i];

                if (nextRow >= 0 && nextRow < 5 && nextCol >= 0 && nextCol < 5) {
                    if (pan[nextRow][nextCol] == targetWords[targetWordsOrder].charAt(combinedWordIdx + 1)
                            || !isOccupied[nextRow][nextCol]) {
                        boolean isSearched = recursiveSearchWord(nextRow, nextCol, combinedWord, combinedWordIdx + 1);
                        if (isSearched)
                            return true;
                    }
                }
            }
        }

        return false;
    }
}