[알고스팟] 보글 게임 - 완전 탐색, 재귀

※ 웹 환경에 최적화된 서식이므로 웹 페이지로 열람함을 권장.

 

보글 게임(링크)

재귀적으로 생각하기

주어지는 단어를 게임판의 알파벳으로 만들 수 있는지 판별하므로 단어의 알파벳 하나와 게임판의 알파벳이 일치하는지 검사하는 작업 조각을 단어의 알파벳 개수만큼 반복해 문제를 해결한다. 단어의 맨 앞 알파벳과 현재 게임판 위치의 알파벳을 비교해 일치하면 나머지 글자로 이루어진 단어를 넘기며 재귀 호출한다.

 

즉, 재귀 함수는 인자로 받는 단어의 첫 알파벳과 게임판의 알파벳이 일치하는지 확인하는 동일한 작업을 반복한다.

재귀 호출에 필요한 입력

찾아야 할 단어와 현재 검사해야 할 게임판의 좌표를 인자로 받는다.

시간 복잡도

시간 안에 동작하는지 확인하기 위해 최악의 경우를 고려해보자. 길이가 n 인 단어가 주어질 때 마지막 글자를 제외한 나머지 (n - 1) 개의 글자가 일치한다면 (n - 1) 번 동안 이웃한 여덟 개의 칸을 계속 검사하게 된다. 즉, 최악의 경우 O(8^n) 의 시간 복잡도를 가진다.

 

#include <iostream>
#include <vector>
#include <string> 
#define BOARD_WIDTH 5
#define BOARD_HEIGHT 5
using namespace std;

vector<vector<char>> board = {
    {'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'}
};

// 인접한 8 개 좌표의 상대적 위치.
const int directions[8][2] = {
    {-1, -1}, {-1, 0}, {-1, 1}, {0, -1},
    {0, 1}, {1, -1}, {1, 0}, {1, 1}
};

bool boggle(string word, int yPos, int xPos) {
    // 인자로 받는 좌표가 게임판을 넘어가는지 확인.
    if (yPos < 0 || BOARD_HEIGHT <= yPos || xPos < 0 || BOARD_WIDTH <= xPos) 
        return false;
    if (board[yPos][xPos] != word[0]) return false;
    if (word.length() == 1) return true;

	// 현재 좌표에서 인접한 8 개의 좌표로 확산.
    for (int next = 0; next < 8; ++next) {
        int nextY = yPos + directions[next][0];
        int nextX = xPos + directions[next][1];

        if (boggle(word.substr(1), nextY, nextX) == true) return true;
    }
    return false;
}

int main() {
    string word = "yes";

    // 'y' is at (2, 2) in the board.
    if (boggle(word, 2, 2)) {
        cout << "Success";
    } else {
        cout << "Failure";
    } 
    cout << endl;

    return 0;
}