[Algorithm Strategies] 01. Exhaustive Search - Boggle

1. Exhaustive Search

1.1 Boggle - Recursive Function

1.1.1 Problem

- 보글은 5 ✕ 5 크기의 알파벳 격자를 가지고 하는 게임

   - 이때 게임의 목적은 상하좌우 / 대각선으로 인접한 칸들의 글자들을 이어서 단어를 찾아내는 것

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

     - 주어진 칸에서 시작해 특정 단어를 찾을 수 있는지 확인하는 문제

1.1.2 Algorithm Strategy

 - 다음 글자가 될 수 있는 칸이 여러 개 있을 때 이 중 어느 글자를 선택해야 할지 미리 알 수 없음

   - 완전 탐색을 이용하여 단어를 찾아 낼 때까지 모든 인접한 칸을 하나씩 시도

     - 그 중 한칸이라도 단어를 찾을 수 있으면 성공, 어느 칸을 선택해도 답이 없으면 실패

 - 위치에 있는 글자가 원하는 단어의 첫 글자가 아닌 경우 항상 실패

 - 원하는 단어가 한 글자인 경우 항상 성공

1.1.3 implementation

- 보글 게임 판의 해당 위치에서 주어진 단어가 시작하는 지를 반환

bool HasWord(int y, int x, const string& word);

   - 함수를 생성하기 전에 5 ✕ 5 크기의 알파벳 격자를 가지고 하는 게임이므로 8개의 방향을 설정해야 함

     - 따라서 방향에 대한 값들을 미리 생성하여 사용할 수 있도록 설정

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

   - 종료조건 만약 범위 밖에 있는 경우, 격자판의 알파벳의 단어가 원하는 단어가 아닌 경우

   - 단어의 길이가 1인 경우 완성하였으므로 성공

if (!InRange(y, x)) return false; if (board[y][x] != word[0]) return false;
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;

1.1.4 Time Complexity

- 완전 탐색 알고리즘의 시간 복잡도를 계산하는 것은 비교적 단순

   - 가능한 답 후보들을 모두 만들어 보기 때문에, 시간 복잡도는 가능한 후보의 수를 전부 세어 보기만 하면 됨

   - 완전 탐색 알고리즘이 모든 경우에 시간 안에 동작함을 확인하기 위해 후보의 최대 수를 계산

 - 마지막 글자가 도달하기 전에는 주변의 모든 칸에 대해 재귀 호출 실행

   - 각 칸에는 최대 여덟 개의 이웃이 있고 탐색은 단어의 길이 N에 대해 N - 1 단계 진행

     - 따라서 검사하는 후보의 수는 최대 8^{n - 1} = O(8ⁿ)이 되고, 알고리즘의 시간 복잡도가 됨