보글 게임(BOGGLE)

(a) 5x5 알파벳 격자1

U	R	L	P	M
X	P	R	E	T
G	I	A	E	T
X	T	N	Z	Y
X	O	Q	R	S

이러한 알파벳 격자를 이용하여 상하좌우/대각선으로 인접한 칸들의 글자를 이어서 단어를 찾아내는 게임

 

 

 

(b)단어 1 .PRETIY

.	.	.	.	.
.	P	R	.	T
.	.	.	E	T
.	.	.	.	Y
.	.	.	.	.

(c)단어 2 .GIRLE

.	.	L	.	.
.	.	R	.	.
G	I	.	.	.
.	.	.	.	.
.	.	.	.	.

(d)단어 3 .REPEAT

.	.	.	P	.
.	.	R	E	.
.	.	A	.	.
.	T	.	.	.
.	.	.	.	.

(e) 5x5 알파벳 격자2

N	N	N	N	S
N	E	E	E	N
N	E	Y	E	N
N	E	E	E	N
N	N	N	N	N

(e)에서 YES를 찾고 싶을땐? 여기서 YES로 연결되는 E는 오른쪽 위 칸 하나.

Y에서 인접한 E만 살펴보면 어느 E를 따라가야 답을 찾을 수 있는 지 알 수 없으므로 완전탐색을 이용함.

const int dx[8] = { -1, -1, -1 , 1, 1, 1, 0, 0};
const int dy[8] = { -1, 0, 1, -1, 0, 1, -1, 1);

bool hasWord(int y, int x, const string& word){
	// 시작 위치가 범위 밖이면 무조건 실패
    if(!inRange(y, x)) return false;
    // 첫 글자가 일치하지 않으면 실패
    if(board[y][x] != word[0]) return false;
    //단어 길이가 1이면 성공
    if(word.size() == 1) return true;
    //인접한 여덟 칸을 검사
    for(int direction = 0; direction < 8; ++direction){
    	int nextY = y + dy[direction], nextX = x+ dx[direction];
        //다음 칸이 범위 안에 있는지, 첫 글자는 일치하는지를 확인할 필요가 없음
        if(hasWord(nextY, nextX, word.substr(1)))
        	return true;
     }
     return false;
}