[알고리즘 / 알고스팟] 보글 Boggle

문제

보글(Boggle) 게임은 그림 (a)와 같은 5x5 크기의 알파벳 격자인
게임판의 한 글자에서 시작해서 펜을 움직이면서 만나는 글자를 그 순서대로 나열하여 만들어지는 영어 단어를 찾아내는 게임입니다. 펜은 상하좌우, 혹은 대각선으로 인접한 칸으로 이동할 수 있으며 글자를 건너뛸 수는 없습니다. 지나간 글자를 다시 지나가는 것은 가능하지만, 펜을 이동하지않고 같은 글자를 여러번 쓸 수는 없습니다.

예를 들어 그림의 (b), (c), (d)는 각각 (a)의 격자에서 PRETTY, GIRL, REPEAT을 찾아낸 결과를 보여줍니다.

보글 게임판과 알고 있는 단어들의 목록이 주어질 때, 보글 게임판에서 각 단어를 찾을 수 있는지 여부를 출력하는 프로그램을 작성하세요.

주의: 알고리즘 문제 해결 전략 6장을 읽고 이 문제를 푸시려는 분들은 주의하세요. 6장의 예제 코드는 이 문제를 풀기에는 너무 느립니다. 6장의 뒷부분과 8장을 참조하세요.

입력

입력의 첫 줄에는 테스트 케이스의 수 C(C <= 50)가 주어집니다. 각 테스트 케이스의 첫 줄에는 각 5줄에 5글자로 보글 게임판이 주어집니다. 게임판의 모든 칸은 알파벳 대문자입니다.
그 다음 줄에는 우리가 알고 있는 단어의 수 N(1 <= N <= 10)이 주어집니다. 그 후 N줄에는 한 줄에 하나씩 우리가 알고 있는 단어들이 주어집니다. 각 단어는 알파벳 대문자 1글자 이상 10글자 이하로 구성됩니다.

출력

각 테스트 케이스마다 N줄을 출력합니다. 각 줄에는 알고 있는 단어를 입력에 주어진 순서대로 출력하고, 해당 단어를 찾을 수 있을 경우 YES, 아닐 경우 NO를 출력합니다.

예제 입력

1
URLPM
XPRET
GIAET
XTNZY
XOQRS
6
PRETTY
GIRL
REPEAT
KARA
PANDORA
GIAZAPX

예제 출력

PRETTY YES
GIRL YES
REPEAT YES
KARA NO
PANDORA NO
GIAZAPX YES

풀이

동적 계획법 문제입니다. 동적계획법을 통해 중복 검색을 제거하는게 키포인트입니다.

검색 결과를 캐쉬 할 5 x 5 x 10 ([행][렬][array index]) 3차원 행렬을 생성하고, 모든 값을 1로 초기화 해줍니다.

그리고 단어의 array index를 입력으로 하여 이후 string을 찾는 재귀함수를 작성합니다.

이때 재귀함수에서 8방향 중 cache 행렬의 값이 0인 방향으로만 string을 찾을 수 있는 지 확인해야 합니다.

만약 8방향 모두 일치하는 string을 찾을 수 없다면 cache 행렬을 [행][렬][array index] = 0으로 설정하도록 하면 됩니다.

답안

#include <stdio.h>
#include <string.h>

char board[5][6];
char cache[5][5][10];
char word[11];
int wordLength;
int direction[8][2] = {{-1, -1}, {0, -1}, {1, -1}, {-1, 0}, {1, 0}, {-1, 1}, {0, 1}, {1, 1}};

int find_sub_str(int row, int column, int index)
{
    int nextIndex = index + 1;
    if (nextIndex >= wordLength) {
        return 1;
    }

    int nextRow;
    int nextColumn;
    for (int dr = 0; dr < 8; dr++) {
        nextRow = row + direction[dr][0];
        nextColumn = column + direction[dr][1];
        if ((nextRow >= 0) && (nextRow < 5)
            && (nextColumn >= 0) && (nextColumn < 5)
            && (cache[nextRow][nextColumn][nextIndex] == 1)
            && (board[nextRow][nextColumn] == word[nextIndex])) {
	    if (find_sub_str(nextRow, nextColumn, nextIndex) == 1) {
				return 1;
            }
        }
    }

    cache[row][column][index] = 0;
    return 0;
}

bool find_str()
{
    for (int row = 0; row < 5; row++) {
        for (int column = 0; column < 5; column++) {
            if ((board[row][column] == word[0]) && (find_sub_str(row, column, 0) == 1)) {
                return true;
            }
        }
    }
    return false;
}

int main()
{
    int tc, num;
    scanf("%d", &tc);
    for (int test = 0; test < tc; test++) {
        for (int i = 0; i < BOARD_SIZE_; i++) {
            scanf("%s", board[i]);
        }

        scanf("%d", &num);
        for (int i = 0; i < num; i++) {
            scanf("%s", word);
            wordLength = strlen(word);

            memset(cache, 1, sizeof(cache));

            if (find_str()) {
                printf("%s YES\n", word);
            } else {
                printf("%s NO\n", word);
            }
        }
    }

    return 0;
}