[알고스팟/C,C++] BOGGLE: 보글 게임

www.algospot.com/judge/problem/read/BOGGLE

algospot.com :: BOGGLE

흔히 '종만북'이라 불리는 '알고리즘 해결 전략' 책에는 난이도: 하로 소개되고 있습니다. 시간제한이 빡빡하기 때문에 완전 탐색이 아닌 동적 계획법(DP)을 이용해 풀어야 하는데 생각보다 꽤 애먹었습니다.. 결국 다른 분들의 해답을 보고 이해한 뒤 다시 풀어 성공하게 되었네요..

보드판은 5 x 5의 2차원 배열 형태로 주어지는데요. 각 위치에서 해당 단어를 찾을 수 있는지 탐색해야 합니다. 좌표 [0, 0] 기준으로는 [0, 0]의 단어를 체크한 뒤 →, ↘, ↓ 총 3방향으로 다음 탐색 지점을 정할 수 있습니다. [0, 1] 기준으로는 ←, ↙, ↓, ↘, → 5방향으로 탐색 지점을 정할 수 있습니다. 모서리 부분을 제외하고는 총 8방향으로 탐색 지점을 정할 수 있지요. 하지만 여기서 중복이 발생하는데 좌표 [0, 3]을 기준으로 설명드리겠습니다. 좌표 [0, 3]에 해당하는 문자는 P입니다. 그렇기 때문에 찾고자 하는 문자열이 "PRETTY"라면 첫 글자를 찾을 수 있는 지점입니다. 이제 [0, 3]에서 다음 탐색을 이어가 보도록 합시다. [0, 3]에서 탐색을 이어갈 수 있는 지점은 ←, ↙, ↓, ↘, → 으로 5방향입니다. 각 방향에 해당하는 좌표는 [0, 2], [1, 2], [1, 3], [1, 4], [0, 4]입니다. 이중 두 번째 문자인 R을 찾을 수 있는 좌표는 [1, 3]입니다. 이외의 [0, 2], [1, 2], [1, 4], [0, 4]는 두번째 문자인 R을 찾기 위해 다시는 탐색할 필요가 없는 좌표들입니다. 

완전 탐색으로 구현할 경우 이렇게 다시 탐색할 필요가 없게 된 좌표들을 다시 탐색하게 됩니다. 두 번째 문자인 R을 제외하고서 각 1, 3, 4, 5, 6번째 문자에 해당하는 P, E, T, T, Y를 찾을 땐 빨간색 x 표시된 좌표들을 탐색해야 할 수도 있습니다. 하지만 적어도 2번째 문자는 해당 좌표들에 존재하지 않기 때문에 다시 탐색할 필요가 없다는 것이죠. 그렇기 때문에 좌표와 찾을 문자에 해당하는 인덱스의 정보를 담을 수 있게 3차원 배열로 DP 공간을 준비하면 됩니다.

bool findWord(string word)
{
    for (int i = 0; i < 5; i++) {
        for (int j = 0; j < 5; j++) {
            if (board[i][j] == word[0]) {
                DP[i][j][0] = hasword(i, j, 1);
                if (DP[i][j][0] == 1) return 1;
            }
        }
    }

    return 0;
}

찾을 문자열을 받아와 전체 좌표를 돌며 첫 번째 문자를 찾을 수 있는지 탐색한 후 찾을 수 있다면 이후 문자들을 탐색하는 hasWord 함수를 호출하게 됩니다. 그리고 해당 보드판에서 문자열을 찾을 수 있는지 없는지 반환해주는 함수입니다.

int hasword(int y, int x, int index) {
    int& ret = DP[y][x][index];
    if (ret != -1) return ret;
    if (index == word.size()) return ret = 1;
    for (int i = 0; i < 8; i++) {
        int next_y = y + Direction[i][0];
        int next_x = x + Direction[i][1];
        if (next_y < 0 || next_y > 4 || next_x < 0 || next_x > 4) continue;
        if (board[next_y][next_x] == word[index]) {
            ret = hasword(next_y, next_x, index + 1);
            if (ret) return ret;
        }
    }

    return ret = 0;
}

첫 번째 문자를 찾은 이후 나머지 문자들을 찾는 함수입니다. 좌표들을 탐색하며 문자열 중 찾아야 할 문자를 찾으면 다시 자기 자신을 재귀 호출합니다. 이 과정에서 DP[y][x][index] 에 해당 문자를 찾을 수 있는지 값을 저장하기 때문에 해당 인덱스에 해당하는 문자를 찾을 수 없다면 그 좌표는 다시 탐색하지 않습니다. 해당 문자를 찾을 수 있는지 없는지가 메모리에 저장되어있기 때문에 그 값만 반환하면 됩니다. 여기서 중요한 것이 있는데 재귀 호출의 구조를 띠고 있기 때문에 첫 번째 문자부터 마지막 직전의 문자까지 찾았더라도 마지막 문자를 찾을 수 없다면 거쳐온 탐색 지점들은 모두 0이 반환되어 저장됩니다. 즉 중간의 문자들을 찾을 수 있는 지점이더라도 이미 마지막 문자까지 찾아 문자열을 완성 시킬 수 없는 지점인 것을 알았기 때문에 그곳은 다시 방문하지 않습니다. 한마디로 정리하면 DP[y][x][index] 는 해당 좌표에서 문자열 중 인덱스에 해당하는 문자를 찾고 마지막 문자까지 찾을 수 있는 지점인가를 나타내는 값이 담겨있다고 생각하시면 됩니다.

#include<iostream>
#include<vector>
#include<cstring>

using namespace std;

char board[5][6];
string word;
int DP[5][5][11];
int Direction[8][2] = {
    {-1, -1}, {-1, 0}, {-1, 1}, {0, 1}, {1, 1}, {1, 0}, {1, -1}, {0, -1}
};

int hasword(int y, int x, int index) {
    int& ret = DP[y][x][index];
    if (ret != -1) return ret;
    if (index == word.size()) return ret = 1;
    for (int i = 0; i < 8; i++) {
        int next_y = y + Direction[i][0];
        int next_x = x + Direction[i][1];
        if (next_y < 0 || next_y > 4 || next_x < 0 || next_x > 4) continue;
        if (board[next_y][next_x] == word[index]) {
            ret = hasword(next_y, next_x, index + 1);
            if (ret) return ret;
        }
    }

    return ret = 0;
}

bool findWord(string word)
{
    for (int i = 0; i < 5; i++) {
        for (int j = 0; j < 5; j++) {
            if (board[i][j] == word[0]) {
                DP[i][j][0] = hasword(i, j, 1);
                if (DP[i][j][0] == 1) return 1;
            }
        }
    }

    return 0;
}

int main(void)
{
    int c; cin >> c;

    for (int i = 0; i < c; i++) {
        for (int j = 0; j < 5; j++) {
            cin >> board[j];
        }
        
        int n; cin >> n;

        for (int i = 0; i < n; i++) {
            memset(DP, -1, sizeof(DP));
            cin >> word;
            if (findWord(word)) {
                cout << word << " YES\n";
            }
            else {
                cout << word << " NO\n";
            }

        }
    }

    return 0;
}