[Algospot] BOGGLE(재귀 호출, 동적계획법)

#. 문제 

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

* 이 문제의 저작권은 Algospot에 있습니다.

보글(Boggle) 게임은 그림 (a)와 같은 5x5 크기의 알파벳 격자인 게임판의 한 글자에서 시작해서 펜을 움직이면서 만나는 글자를 그 순서대로 나열하여 만들어지는 영어 단어를 찾아내는 게임입니다. 

펜은 상하좌우, 혹은 대각선으로 인접한 칸으로 이동할 수 있으며 글자를 건너뛸 수는 없습니다. 지나간 글자를 다시 지나가는 것은 가능하지만, 펜을 이동하지않고 같은 글자를 여러번 쓸 수는 없습니다.

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

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

입력

입력의 첫 줄에는 테스트 케이스의 수 C(C <= 50)가 주어집니다. 각 테스트 케이스의 첫 줄에는 각 5줄에 5글자로 보글 게임판이 주어집니다. 게임판의 모든 칸은 알파벳 대문자입니다.

그 다음 줄에는 우리가 알고 있는 단어의 수 N(1 <= N <= 10)이 주어집니다. 그 후 N줄에는 한 줄에 하나씩 우리가 알고 있는 단어들이 주어집니다. 각 단어는 알파벳 대문자 1글자 이상 10글자 이하로 구성됩니다.

출력

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

#. 문제 해결 과정

  1. 문제를 읽고 이해하기

  2. 문제를 익숙한 용어로 재정의 + 추상화 

    - 목적은 한 글자에서 시작해서 상하좌우/대각선으로 인접한 칸들의 글자들을 이어서 단어를 찾아내는 것

    - 글을 건너뛸 수 없음

    - 지나간 글자를 다시 지나가는 것은 가능하지만, 펜을 이동하지 않고 같은 글자를 여러번 쓸 수 없음

    - 조건 :

        테스트 케이스의 수 C(C <= 50)

        단어의 수 N(1 <= N <= 10)

  3. 어떻게 해결할지 계획 세우기(알고리즘, 자료구조 선택) -> 풀이

  4. 계획 검증하기(수행 시간, 사용 메모리 확인)

    - 각 칸에는 최대 8개의 이웃 칸, 탐색의 단어의 길이는 N에 대하여 N-1단계가 진행 -> 최대 검사 후보의 수 8^(N-1)

  5. 계획 수행하기

  6. 어떻게 풀었는지 돌아보고, 개선할 방법이 있는지 찾아보기

#. 풀이

  1. 테스트 케이스 수(C <= 50) 입력받기

  2. 입력받은 알파벳으로 게임판 배열 생성

  3. 단어의 수 (1 <= N <= 10) 입력받기

  4. 입력된 단어(1글자이상 10글자 이하)를 입력받고 hasWord 함수를 통해 단어가 있는지 없는지 bool 자료형으로 반환

  5. hasWord는 (int y, int x, String word)를 인자로 갖고 재귀 호출을 사용하여 구현

    - 기저 사례

      ㄴ(y,x)에 있는 글자가 원하는 단어의 첫 글자가 아닌 경우 항상 실패

      ㄴ위 상황이 아닌 경우, 원하는 단어가 한 글자인 경우 항상 성공

  6. 해당 단어와 return된 bool 결과를 출력

#. 코드

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.ArrayList;
 
public class C63_ans {
    static int[] dx = {-1, 0, 1, 1, 1, 0, -1, -1};
    static int[] dy = {-1, -1, -1, 0, 1, 1, 1, 0};
    static ArrayList<String> board = new ArrayList<String>();
    static int C;    // number of testcase
    static int N;    // number of word
    
    public static void run() throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
 
        // 1. 테스트 케이스 수 입력받기
        C = Integer.parseInt(br.readLine());
        if(C > 50) {
            bw.write("Error :: C(testCase) <= 50");
            bw.flush();
            System.exit(0);
        }
        
        for(int tc=0; tc<C; tc++) {
            // 2. 게임판 생성
            for(int input=0; input<5; input++) {
                board.add(br.readLine());
            }
            // 3.단어의 수 입력 받기
            N = Integer.parseInt(br.readLine());
            if(N<1 || N>10) {
                bw.write("Error :: 1 <= N(number of word) <= 10");
                System.exit(0);
            }
            // 4. 단어를 입력받은 후 hasWord함수에서 단어 여부 확인
            for(int now=0; now<N; now++) {
                String word = br.readLine();
                boolean ret = false;
                for(int y=0; y<5; y++) {
                    for(int x=0; x<5; x++) {
                        ret = hasWord(y,x,word);
                        if(ret==true) break;
                    }
                    if(ret==true) break;
                }
                // 6. 결과 출력 
                bw.write(String.format("%s %s\n", word, ret?"YES":"NO"));
            }
        }
        bw.close();
    }
    // 5. 입력된 단어가 게임판에 있는지 확인하는 함수 
    public static boolean hasWord(int y, int x, String word) {
        // 기저 사례 1 : 범위를 벗어난 경우
        if(y<0 || y>4 || x<0 || x>4) return false;
        // 기저 사례 2 : 단어의 첫 글자가 일치하지 않을 경우
        if(board.get(y).charAt(x) != word.charAt(0)) return false;
        // 기저 사례 3 : 단어 길이가 1일  경우
        if(word.length() == 1) return true;
        // 인접한 칸을 검사
        for(int dir=0; dir<8; dir++) {
            int surY = y + dy[dir];
            int surX = x + dx[dir];
            if(hasWord(surY, surX, word.substring(1)))
                return true;
        }
        return false;
    }
    
    public static void main(String[] args) throws Exception {
        C63_ans.run();
    }
}
 

> 동적계획법을 활용한 방법

#. 결과

  - Input --------------------------------------------------------

1

URLPM

XPRET

GIAET

XTNZY

XOQRS

6

PRETTY

GIRL

REPEAT

KARA

PANDORA

GIAZAPX

------------------------------------------------------------------

  - Output --------------------------------------------------------

PRETTY YES

GIRL YES

REPEAT YES

KARA NO

PANDORA NO

GIAZAPX YES

------------------------------------------------------------------