[Algorithm] 보글(Boggle) 게임 문제 (C++)

다음 도서를 참고하여 작성하였습니다.

http://www.kyobobook.co.kr/product/detailViewKor.laf?mallGb=KOR&ejkGb=KOR&barcode=9788966260546 

알고리즘 문제 해결 전략 세트 - 교보문고

---

문제 

보글 게임은 다음과 같이 5 x 5 크기의 알파벳 격자를 가지고 하는 게임입니다. 

목적은 상하좌우/대각선으로 인접한 칸들의 글자를 이어서 단어를 찾아내는 것입니다. 

 

보글 게임

예를들어 위의 그림에서 (b), (c), (d)는 각각 PRETTY, GIRL, REPEAT 등의 단어를 찾은 것입니다.

각 글자들은 대각선으로도 이어질 수 있으며, 한 글자가 두 번 이상 사용될 수 있습니다.

주어진 칸에서 시작해서 특정 단어를 찾을 수 있는지 확인하는 코드를 작성하세요.

 

---

풀이

문제를 푸는 가장 간단한 방법은 완전 탐색을 이용하여, 단어를 찾아낼 때 까지 모든 인접한 칸을 하나씩 시도하여, 한 칸이라도 찾을 수 있으며 성공이고, 어느 칸을 선택하더라도 답이 없다면 실패가 됩니다.

 

만약 주어진 칸에 원하는 단어의 첫 글자가 아닌 경우는 항상 실패이며, 주어진 칸이 원하는 단어이며 원하는 단어가 한 글자인 경우는 항상 성공입니다.

---

구현

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

// (y, x)에서 주어진 단어가 시작하는 지 여부 반환(True or False)
bool hasWord(int y, int x, string& word){
    // 시작 위치가 범위 밖이면 무조건 실패
    if (y < 0 || x < 0 || y > 4 || x > 4)
        return false;
        
    // 첫 글자가 일치하지 않으면 실패
    if (board[y][x] != word[0])
        return false;
        
    // 첫 글자가 일치하며 단어의 길이가 1인 경우 성공
    if (word.size() == 1) 
        return true;
        
    // 인접한 8칸 검사
    for(int dir=0; dir < 8; ++dir){
        int nextY = y + dy[dir];
        int nextX = x + dx[dir];
        
        // 문자열의 첫 문자는 일치하므로, 첫 문자를 제외하여 재귀함수 호출
        if(hasWord(nextY, nextX, word.substr(1)))
            return true;
    }
    return false;
}

---

시간복잡도

각 칸에 최대 8개의 이웃들이 있으며, 탐색은 단어길이 N에 대해 N-1단계 진행되므로 최대 검사 후보의 수는 

8^N-1이다. 따라서 시간복잡도는 O(8^N) 입니다.