chapter06 : 보글게임

문제

보글(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.util.*;
import java.io.*; 
 
 
public class Main {   
  
  static String[][] board = new String[5][5]; 
  static String[] words;
  static boolean[] visited;
  static boolean flag = false; 
  static int[][] DELTAS = { { -1, -1 }, { -1, 0 }, { -1, 1 }, { 0, -1 }, { 0, 1 }, { 1, -1 }, { 1, 0 }, { 1, 1 } };
  
  
  static void hasWord( int row, int col, int x ) {
    
    if( flag ) return;
    
    if ( x >= words.length ) {
      flag = true;
      return;
    }
    
    if ( !board[row][col].equals( words[x] ) || visited[x] ) return;
    
    for ( int i = 0; i < 8; ++i ) { 
        
      visited[x] = true;
      int ny = DELTAS[i][0] + row, nx = DELTAS[i][1] + col;
      if ( ny >= 0 && ny < 5 && nx >= 0 && nx < 5 ) {
        hasWord( ny, nx, x+1 );
      }
      visited[x] = false; 
      
    }
  }
  
  
  // main  
  public static void main( String[] args ) throws Exception {
    
    // Please Enter Your Code Here 
    BufferedWriter bw  = new BufferedWriter( new OutputStreamWriter( System.out ) );
    BufferedReader br  = new BufferedReader( new InputStreamReader( System.in ) );
    StringBuilder sb   = new StringBuilder();
    
    int C = Integer.parseInt( br.readLine() );
    while ( C --> 0 ) {
      
      for ( int row = 0; row < 5; ++row ) {
        String[] lines = br.readLine().toString().split("");
        for ( int col = 0; col < 5; ++col ) {
          board[row][col] = lines[col];
        }  
      } 
      
      int N = Integer.parseInt( br.readLine() );
      for ( int q = 0; q < N; ++q ) {
        
        flag    = false;
        String str = br.readLine().toString();
        words   = str.toString().split("");
        visited = new boolean[ words.length ];
        
        for ( int row = 0; row < 5; ++row ) {
          for ( int col = 0; col < 5; ++col ) {
            hasWord( row, col, 0);
          }
        }
        
        if ( flag ) sb.append(str + " YES").append("\n");
        else sb.append(str + " NO").append("\n");
        
      }
      
    }
    
    bw.write( sb.toString() );
    bw.flush();
    bw.close();
    br.close(); 
  } 
  
  
} 

 

개선 코드

import java.util.*;
import java.io.*; 
 
 
public class Main {   
  
  static String[][] board = new String[5][5]; 
  static String[] words; 
  static boolean flag = false; 
  static int[][] DELTAS = { { -1, -1 }, { -1, 0 }, { -1, 1 }, { 0, -1 }, { 0, 1 }, { 1, -1 }, { 1, 0 }, { 1, 1 } };
  
  
  static boolean hasWord( int row, int col, int x ) {
    
    // 기저사례 :  x가 단어의 길이만큼이 되었을 때, 성공
    if ( x >= words.length ) return true;
    // 기저사례 : 해당 단어가 보드의 단어와 같지 않다면 바로 종료한다.
    if ( !board[row][col].equals( words[x] ) ) return false;
    
    // 다음단계로 진행을 한다.
    for ( int i = 0; i < 8; ++i ) {  
      int ny = DELTAS[i][0] + row, nx = DELTAS[i][1] + col;
      if ( ny >= 0 && ny < 5 && nx >= 0 && nx < 5 ) if (hasWord( ny, nx, x+1 )) return true; 
    }
    
    return false;
  }
  
  
  // main  
  public static void main( String[] args ) throws Exception {
    
    // Please Enter Your Code Here 
    BufferedWriter bw  = new BufferedWriter( new OutputStreamWriter( System.out ) );
    BufferedReader br  = new BufferedReader( new InputStreamReader( System.in ) );
    StringBuilder sb   = new StringBuilder();
    
    // 주어진 입력값을 읽어들인다.
    int C = Integer.parseInt( br.readLine() );
    while ( C --> 0 ) {
      
      for ( int row = 0; row < 5; ++row ) {
        String[] lines = br.readLine().toString().split("");
        for ( int col = 0; col < 5; ++col ) 
          board[row][col] = lines[col];
      } 
      
      int N = Integer.parseInt( br.readLine() );
      for ( int q = 0; q < N; ++q ) {
        
        flag    = false;
        String str = br.readLine().toString();
        words   = str.toString().split(""); 
        
        out : for ( int row = 0; row < 5; ++row ) {
          for ( int col = 0; col < 5; ++col ) {
            flag = hasWord( row, col, 0);
            // 한번 성공했으면 더 이상 체크할 필요가 없으므로 탈출한다.
            if ( flag ) break out;
          }
        }
        
        if ( flag ) sb.append(str + " YES").append("\n");
        else sb.append(str + " NO").append("\n"); 
      }
      
    }
    
    bw.write( sb.toString() );
    bw.flush();
    bw.close();
    br.close(); 
  }  
  
} 

 

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

algospot.com :: BOGGLE