알고스팟 Boggle

문제

보글(Boggle) 게임은 그림 (a)와 같은 5x5 크기의 알파벳 격자인
게임판의 한 글자에서 시작해서 펜을 움직이면서 만나는 글자를 그 순서대로 나열하여 만들어지는 영어 단어를 찾아내는 게임입니다. 펜은 상하좌우, 혹은 대각선으로 인접한 칸으로 이동할 수 있으며 글자를 건너뛸 수는 없습니다. 지나간 글자를 다시 지나가는 것은 가능하지만, 펜을 이동하지않고 같은 글자를 여러번 쓸 수는 없습니다.

예를 들어 그림의 (b), (c), (d)는 각각 (a)의 격자에서 PRETTY, GIRL, REPEAT을 찾아낸 결과를 보여줍니다.

보글 게임판과 알고 있는 단어들의 목록이 주어질 때, 보글 게임판에서 각 단어를 찾을 수 있는지 여부를 출력하는 프로그램을 작성하세요.

주의: 알고리즘 문제 해결 전략 6장을 읽고 이 문제를 푸시려는 분들은 주의하세요. 6장의 예제 코드는 이 문제를 풀기에는 너무 느립니다. 6장의 뒷부분과 8장을 참조하세요.

입력

입력의 첫 줄에는 테스트 케이스의 수 C(C <= 50)가 주어집니다. 각 테스트 케이스의 첫 줄에는 각 5줄에 5글자로 보글 게임판이 주어집니다. 게임판의 모든 칸은 알파벳 대문자입니다.
그 다음 줄에는 우리가 알고 있는 단어의 수 N(1 <= N <= 10)이 주어집니다. 그 후 N줄에는 한 줄에 하나씩 우리가 알고 있는 단어들이 주어집니다. 각 단어는 알파벳 대문자 1글자 이상 10글자 이하로 구성됩니다.

출력

각 테스트 케이스마다 N줄을 출력합니다. 각 줄에는 알고 있는 단어를 입력에 주어진 순서대로 출력하고, 해당 단어를 찾을 수 있을 경우 YES, 아닐 경우 NO를 출력합니다.

---

해설

처음 6장을 보고, 내가 푼 문제 풀이이다. 

이후 8장을 참조하여 수정하도록 하겠다.

public static boolean hasWord(int y, int x, String word, char[][] table, int n){
        // y : [y][]
        // x : [][x]
        // word : 골라야 할 단어
        // table : 판
        // n : n번째 문자, 골라야 할 문자
        
        int[] pointX = {-1, 0, 1, 1, 1, 0, -1, -1};
        int[] pointY = {-1, -1, -1, 0, 1, 1, 1, 0};
        
        // 기저 사례 1 : 시작 위치가 범위 밖이면 실패
        if(y >= table.length || y < 0) return false;
        if(x >= table[0].length || x < 0) 
        
        // 기저 사례 2 : 시작 위치가 단어의 n번째 글자와 다르면 실패
        if(table[y][x] != word.charAt(n)){
            return false;
        }
        // 기저 사례 3 : 단어 길이가 같고, 시작위치와 문자가 같은 성공 => 여기서 중요한 게 위 기저 사례 2에서 글자가 다른 경우를 제거해줬기 때문에, 앞의 조건은 무의미
        if(table[y][x] == word.charAt(n) && n == word.length() - 1){
            System.out.println("true");
            return true;
        }
        return hasWord(y + pointY[0], x + pointX[0], word, table, n + 1)
                || hasWord(y + pointY[1], x + pointX[1], word, table, n + 1)
                || hasWord(y + pointY[2], x + pointX[2], word, table, n + 1)
                || hasWord(y + pointY[3], x + pointX[3], word, table, n + 1)
                || hasWord(y + pointY[4], x + pointX[4], word, table, n + 1)
                || hasWord(y + pointY[5], x + pointX[5], word, table, n + 1)
                || hasWord(y + pointY[6], x + pointX[6], word, table, n + 1)
                || hasWord(y + pointY[7], x + pointX[7], word, table, n + 1);
    }

 

하나하나 8방향을 탐색하는 과정을 for문으로 돌려도 됐는데, 그렇게 생각을 못 한 게 아쉽다.

느낀 점

• 문제 풀이에 있어서 기저 사례를 먼저 적는 것의 중요성과 기저 사례의 순서도 중요하다는 것을 알 수 있었다.
• 기저 사례 2를 보면 앞 조건은 기저 사례 1에 의해 이미 걸러진 조건이기 때문에 무의미함을 알 수 있다.