알고리즘 문제 해결 BOGGLE

#Boggle

무식하게 푼다. 일명 (brute-force)는 컴퓨터의 빠른 속도를 이용해 가능한 경우의 수를 일일이 나열하면서 답을 찾는 방법을 의미한다.

예를 들면 두 점 사이의 최단 경로를 찾는 문제라면 두 점 사이의 경로들을 하나 하나 전부 만들어서 그중 가장 짧은 것을 찾는 방법 이다. 이러한게 “무식한” 알고리즘의 좋은 예이다.

이러한 가능한 모든 경우의 수를 세는 문제를 완전 탐색이라고 부릅니다.

재귀 호출과 완전 탐색

우리가 들여다보는 범위가 작아지면 작아질수록 각 조각들의 형태가 유사해지는 작업들을 볼 수 가 있습니다. 완전히 같은 코드를 반복해 실행하는 for 같은 반복문이 이와 같은 예시 입니다.

이런 작업에 유용하게 사용되는 개념이 재귀 함수, 재귀 호출 입니다.

쪼개지지 않은 가장 작은 작업들을 가르켜 재귀 호출의 기저 사례(base case)라고 합니다.

예제: 보글 게임(난이도 :하)

5x5 배열에서 입력한 단어가 있는지 없는지 찾는 알고리즘입니다. 글자 하나 하나 이어지는지 확인 하기 위해 재귀를 사용하게 됩니다.

 

1
URLPM
XPRET
GIAET
XTNZY
XOQRS
6
PRETTY
GIRL
REPEAT
KARA
PANDORA
GIAZAPX

이 문제의핵심은 더 이상 분해되지 않는 기저 사례를 잘 찾는 것 인거 같다.

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.*;

public class Main {
    static char [][] boggle = new char[5][5];
    static int [] dx = {-1,-1,-1,0,0,1,1,1};
    static int [] dy = {-1,0,1,-1,1,-1,0,1};
    static ArrayList <String> arr= new ArrayList<>();
     public static boolean search(int x, int y, String word){
        if(!boundary(x,y)){
            return false;
        }
        if(boggle[x][y] != word.charAt(0)){
            return false;
        }
        if(word.length() ==1){
            return true;
        }
        for(int i=0; i<8; i++){
            int nextX = x+dx[i];
            int nextY = y+dy[i];
            if(search(nextX,nextY,word.substring(1))){
                return true;
            }
        }
        return false;

    }
     public static boolean boundary(int x, int y){
         if((x>=0&&y>=0)&&(x<5&&y<5)) return true;
         else {
             return false;
         }

    }
    public static void main(String[] args) throws Exception {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st= new StringTokenizer(br.readLine());
        int N = Integer.parseInt(st.nextToken());
        for(int z = 0; z<N; z++){
            for(int i=0; i<5; i++){
                st= new StringTokenizer(br.readLine());
                String word = st.nextToken();
                for(int j=0; j<5; j++){
                    boggle[i][j] = word.charAt(j);
                }
            }
            int C = Integer.parseInt(br.readLine());
            String [] answer = new String [C];
            for(int i=0; i<C; i++){
                String word = br.readLine();
                answer[i] = word;
                for(int j=0; j<5; j++){
                    for(int k=0; k<5; k++){
                        if(search(j,k,word)){
                            arr.add(word);
                        }
                    }
                }
            }
            for(int i=0; i<C; i++){
                if(arr.contains(answer[i])){
                    System.out.println(answer[i]+ " "+"YES");
                }
                else{
                    System.out.println(answer[i]+" "+"NO");
                }
            }
        }
    }
}