[Algospot] 알고스팟 BOGGLE 보글 게임

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

 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

▶ 동적계획법(Dynamic Programming, DP) 

동적계획법(Dynamic Programming, DP)

 

펜이 움직일 수 있는 가동범위를 재귀적으로 구현할 수 있습니다.

※ 이미 탐색한 알파벳을 재사용할 수 있지만 다른 곳을 탐색한 후에 재활용할 수 있다!

    그렇기에 아래의 게임판에서  MTTTY는 NO이며 / MTTTTY는 YES를 출력해야 한다.

But, 주먹구구 방식의 완전탐색의 경우에는 TLE 발생 O(8n)

 Input 

1

AAAAA

AAAAA

AAAAA

AAAAA

AAAAA

1

AAAAAH

 

 Output 

AAAAAH NO

'H'란 문자가 게임판에 없기 때문에 "NO"를 출력합니다.

시작위치에서 시작하는 모든 후보들을('A') 전부 검사하면서 

단어의 끝에 도달해서야 답을 찾을 수 없다는 것을 알게됩니다.

 

재귀함수로 구현 ▶ 시간 초과 발생

① 위치(x,y)에 있는 알파벳이 단어의 첫 글자인 경우 탐색 시작.

② 첫글자가 일치하는 곳에서부터 8방향(상하좌우 + 대각선)으로 

     단어의 글자를 맞출 수 있는지 재귀적으로 탐색

import java.util.Scanner;

public class Main {
    static char[][] board;
    static String str;
    static int[] dx,dy;
    static boolean answer;
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        
        int C, N;
        // Test Case 개수
        C = Integer.parseInt(sc.next());
        
        // 상하좌우 + 대각선(11시,1시,5시,7시)
        dx = new int[]{-1, 1, 0, 0, -1, -1, 1, 1};
        dy = new int[]{0, 0, -1, 1, -1, 1, 1, -1};
        
        // 5줄 * 5글자 = 25개 칸의 보드판
        board = new char[5][5];
        
        // Test Case 개수 만큼
        for(int i=0; i<C; i++) {
            // board판 칸에 글자 부여
            for(int j=0; j<5; j++) {
                str = sc.next();
                for(int k=0; k<str.length(); k++) {
                    // char 형을 저장
                    board[j][k] = str.charAt(k);
                }
            }
            
            // 단어의 개수
            N = Integer.parseInt(sc.next());
            for(int j=0; j<N; j++) {
                str = sc.next();
                System.out.print(str + " ");
                // board판에서 찾을 수 있는 단어인지 확인
                if(checkBoard()) {
                    System.out.println("YES");
                }else {
                    System.out.println("NO");
                }
            }
        }
    }

    static boolean checkBoard() {
        for(int i=0; i<5; i++) {
            for(int j=0; j<5; j++) {
                // 만약 첫글자가 일치한다면 탐색 시작(상하좌우 + 대각선)
                if(str.charAt(0) == board[i][j]) {
                    // 현재위치와 탐색할 문자 인덱스로 시작한다.
                    if(searchStr(new Node(i,j), 1)) {
                        return true;
                    }
                }
            }
        }
        return false;
    }

    static boolean searchStr(Node node, int idx) {
        // 해당 문자열을 board판에서 모두 찾았다.
        if(idx >= str.length()) {
            return true;
        }
        // 탐색위치 좌표(상하좌우 + 대각선)
        for(int i=0; i<8; i++) {
            int next_x = node.x + dx[i];
            int next_y = node.y + dy[i];
            
            // 배열을 초과하지 않는 범위에서
            if(next_x < 0 || next_y < 0) continue;
            if(next_x >= 5 || next_y >= 5) continue;
            
            
            // 찾고자 하는 문자에 해당된다면(char형)
            // 재귀를 이용해서 다음 찾을 문자의 인덱스와 위치를 넘기면서 탐색을 이어간다.
            // 모든 경우를 탐색하는데 이는 board의 크기가 작기 때문에 가능
            if(board[next_x][next_y] == str.charAt(idx)) {
                if(searchStr(new Node(next_x, next_y), idx+1)) {
                    return true;
                }
            }
        }
        return false;
    }
}

class Node{
    int x,y;
    public Node(int x, int y) {
        this.x = x;
        this.y = y;
    }
}

 

동적 계획법(DP)을 이용한 풀이

boolean[][][] cache를 통해 중복 방문을 제외시킵니다.

게임판의 크기 5 × 5이면서, 단어의 글자수가 최대 10이므로 [5][5][10]으로 할당

특정 단어(Word)의 k번째 글자를 (x, y)에서 방문하여 이미 확인한 것을 의미합니다.

 

 

ex) 'PRETTY' 글자를 찾는 과정 예시

chche[0][3][0] = cache[1][2][1] = cache[2][3][2] = true

cache[1][1][0] = true가 되며, 다음 방문할 cache[1][2][1]은 이미 방문하였으므로 탐색 종료

즉, 이미 확인한 단계는 재확인 하지 않는 것입니다.

---

#include <iostream>
#include <cstring>
using namespace std;
 
int dx[8] = { -1,0,1,1,1,0,-1,-1 };
int dy[8] = { 1,1,1,0,-1,-1,-1,0 };
char board[5][5];
int N, test_case;
char word[11];
bool cache[5][5][10];
 
bool searchWord(int x, int y, int idx){
    if(idx == strlen(word)-1) return true;
    if(board[x][y] != word[idx]) return false;
    
    cache[x][y][idx] = 1;
 
    for (int i = 0; i < 8; i++){
        int next_x = x + dx[i];
        int next_y = y + dy[i];
 
        if(next_x < 0 || next_x >= 5 || next_y < 0 || next_y >= 5) continue;
        if(cache[next_x][next_y][idx+1]) continue;
        if(board[next_x][next_y] != word[idx+1]) continue;
        if(searchWord(next_x, next_y, idx + 1)) return true;
    }
 
    return false;
}
 
bool isAvailableWord(){
    for(int x=0; x<5; x++){
        for(int y=0; y<5; y++){
            if(searchWord(x, y, 0)) return true;
        }
    }
    return false;
}
 
int main(void){
    cin >> test_case;
    for (int tc = 0; tc < test_case; tc++){
        for(int i=0; i<5; i++){
            scanf("%s", board[i]);
        }
 
        scanf("%d", &N);
        for(int i=0; i<N; i++){
            memset(cache, 0, sizeof(cache));
            scanf("%s", word);
 
            printf("%s ", word);
            if(isAvailableWord()) cout << "YES\n";
            else cout << "NO\n";
        }
    }
    return 0;
}