보글 게임 (골드2)

1. 문제 설명

(1) 5x5 크기의 알파벳 격자 형태에서 주어진 단어를 찾는 게임이다.

 

(2) 상하 좌우, 대각선 등으로 이어질 수 있으며 한 글자가 두 번 이상 사용 가능하다.

 

 

 

 

2. 과정

	1	2	3	4	5
1	a	b	c	d	e
2	f	g	h	i	j
3	k	l	m	n	o
4	p	q	r	s	t
5	u	v	w	x	y

 

( 이때, 찾는 단어 'gmq'라고 가정해보자. 그러면 과정은 다음과 같다. )

1.처음 1행 1열부터 ~ 5행 5열까지 가로 순으로 첫 단어를 기저 사례로 통해 찾아본다.   2.제일 먼저 발견되는 알파벳은 'g'이며, 'm'에 대해서 주변 인접한 단어를 재귀 호출로 찾아본다.   3.재귀 호출 과정에서 오른쪽 아래 대각선 'm'을 찾았고 다시 주변 인접한 단어를 재귀 호출로 찾아본다.   4.재귀 호출 과정에서 왼쪽 아래 대각선 'q'를 찾고 모든 단어들을 찾았음을 확인하고 원점으로 다시 리턴한다.

 

( 이때, 인접한 단어는 아래의 표처럼 (0,0) 기준으로 8개가 둘러쌓였다고 가정한다. )

 

(-1, -1)	(-1, 0)	(-1, 1)
(0, -1)	(0, 0)	(0, 1)
(1, -1)	(1, 0)	(1, 1)

( 그렇다면, 이 부분을 (0,0)을 제외한 나머지 좌표값을 dx, dy 배열을 만들어 사용한다. )

( 사용 방법은 간단하다. 예를 들면, (0,0)에서 단어를 찾았다면, nextX(0+dx[0]), nextY(0+dy[0])로 구해주면 

해당 좌표가 나온다. )

static final int[] dx = { -1, -1, -1, 1, 1, 1, 0, 0 };

static final int[] dy = { -1, 0, 1, -1, 0, 1, -1, 1 };

 

( 주의할 점은 항상 인접한 단어가 8개가 아닐 수도 있기 때문에, 범위를 넘어가는 지 항상 체크해야 한다. )

 

 

3. 기저 사례

(1) 시작 위치가 보드판 범위를 벗어나면 false를 리턴한다.

 

(2) 첫 글자가 일치하지 않으면 false를 리턴한다.

 

(3) 재귀 호출로 인한 단어의 길이가 1이면 true를 리턴한다.

 

 

 

 

4. 입출력 조건 및 예제

입력 조건

(1) 첫 줄에 보드판 X(행)와 Y(열)을 입력받는다. 

( X>=0 && Y>=0 )

 

(2) 두 번째 줄부터 X행(줄)까지 문자열(알파벳)을 넣는다.

 

(3) X+1행(줄)에는 찾아볼 문자열의 입력 개수 N을 입력받는다.

( N>=0 )

 

(4) X+2행(줄)에는 N줄만큼 찾아볼 문자열들을 입력한다.

 

출력 조건

(1) 각 N크기만큼 찾으면 YES, 없다면 NO를 출력한다.

 

입력 예제

5 5
abcde
fghij
klmno
pqrst
uvwxy
3
gmo
gmz
gmq

5. 풀이 및 코드

public class BOGGLE {
    static final int[] dx = { -1, -1, -1,  1,  1,  1,  0,  0 };
    static final int[] dy = { -1,  0,  1, -1,  0,  1, -1,  1 };
    
    // 각각 보드판, 보드판 크기, 찾을 문자열 개수, 찾는 문자열들
    static char[][] board ;
    static int X, Y;
    static int N;
    static String[] searchWords;
    
    static BufferedReader sc = new BufferedReader(new InputStreamReader(System.in));
    static StringBuilder sb = new StringBuilder();
    
    public static void main(String[] args) throws Exception {
        StringTokenizer st = new StringTokenizer(sc.readLine());
        X = Integer.parseInt(st.nextToken());
        Y = Integer.parseInt(st.nextToken());
        
        board = new char[X][Y];
        for(int i=0; i<X; i++) {
            String tmp = sc.readLine();
            for(int j=0; j<Y; j++) {
                board[i][j] = tmp.charAt(j);
            }
        }
        
        N = Integer.parseInt(sc.readLine());
        searchWords = new String[N];
        for(int i=0; i<N; i++) {
            searchWords[i] = sc.readLine();
        }
        
        // 0번부터 입력받은 문자열 개수(N) 크기만큼 반복
        for(int a = 0; a< N; a++) {
            boolean isWord = false;
            
            // 보드판 크기만큼 계속 찾는다.
            for(int i=0; i<X; ++i) {
                for(int j=0; j<Y; ++j) {
                    if(hasWord(i, j, searchWords[a])) {
                        isWord = true;
                        break;
                    }
                }
            }
            
            if(isWord) sb.append(searchWords[a] + " --> YES\n");
            else  sb.append(searchWords[a] + " --> NO\n");
        }
        System.out.println(sb);
    }
    static boolean hasWord(int y, int x, String word) {
        // 기저사례 1 : 시작 위치가 밖이면 무조건 실패
        if(!inRange(y, x)) return false;
        
        // 기저사례 2 : 첫 글자가 일치하지 않으면 실패
        if(board[y][x] != word.charAt(0)) return false;
        
        // 기저사례 3 : 단어 길이가 1이면 성공
        if(word.length() == 1) return true;
        
        // 인접한 여덟 칸을 검사
        for(int direction = 0; direction < 8; ++direction) {
            int nextY = y + dy[direction];
            int nextX = x + dx[direction];
            // 다음 칸이 범위 안에 있는지, 첫 글자는 일치하는지 확인할 필요가 없음.
            if(hasWord(nextY, nextX, word.substring(1))) return true;
        }
        return false;
    }
    
    static boolean inRange(int y, int x) {
        return (x >= 0 && x < X) && (y >= 0 && y < Y);
    }
}

 

 

 

 

6. 시간 복잡도

- 탐색 단어의 길이만큼 재귀 호출이 늘어나기 때문에, 8^n-1 = O(8^n)이 된다.