[ALGOSPOT] 보글게임(BOGGLE)

[ALGOSPOT] 보글게임(BOGGLE)

보글 게임

• 문제
• 답안 제출
• 통계

문제 정보

• • 문제 ID
  • 시간 제한
  • 메모리 제한
  • 제출 횟수
  • 정답 횟수 (비율)
• • BOGGLE
  • 10000ms
  • 65536kb
  • 9446
  • 1521 (16%)
• • 출제자
  • 출처
  • 분류
• • JongMan
  • 알고리즘 문제 해결 전략
  • 보기

문제

보글(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를 출력합니다.

예제 입력

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

예제 출력

PRETTY YES
GIRL YES
REPEAT YES
KARA NO
PANDORA NO
GIAZAPX YES

노트

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
 
public class Main {
    static char[][] map = new char[5][5];
    static final int[] dx = { -1, -1, -1, 1, 1, 1, 0, 0 };
    static final int[] dy = { -1, 0, 1, -1, 0, 1, -1, 1 };
 
    // 5 x 5 보글 게임 판의 해당 위치에서 주어진 단어가 시작하는지를 반환.
    static boolean hasWord(int y, int x, String word) {
        // 1. 시작 위치가 범위 밖이면 무조건 실패
        if (!(y >= 0 && y < 5 && x >= 0 && x < 5)) {
            return false;
        }
        // 2. 첫 글자가 일치하지 않으면 실패
        if (map[y][x] != word.charAt(0)) {
            return false;
        }
        // 3. 단어가 일치하면서 원하는 단어가 한 글자인 경우 항상 성공
        if (word.length() == 1) {
            return true;
        }
        // 인접한 여덟 칸을 검사한다.
        for (int direction = 0; direction < 8; direction++) {
            int nextY = y + dy[direction];
            int nextX = x + dx[direction];
            // word.substring(1)을 하면
            // 첫 번째 index 0을 제외하고 [1...]을 계속해서 수행한다.
            if (hasWord(nextY, nextX, word.substring(1))) {
                return true;
            }
        }
        return false;
    }
    
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        
        int tc = Integer.parseInt(br.readLine());
        while(tc-- > 0) {
            for(int i = 0; i<5; i++) {
                String str = br.readLine();
                map[i] = str.toCharArray();
            }
            
            int nWord = Integer.parseInt(br.readLine());
            while(nWord-- > 0) {
                String word = br.readLine();
                String result = "NO";
                for(int y = 0; y < 5; y++) {
                    for(int x = 0; x < 5; x++) {
                        if(hasWord(y, x, word) && result.equals("NO"))
                            result = "YES";
                    }
                }
                bw.write(word + " " + result);
                bw.newLine();
                bw.flush();
            }
            bw.close();
        }
    }
}