[Algospot] BOGGLE C++

Juppi·2021년 9월 28일
0

Algorithm

목록 보기
1/4

오늘의 문제는 완전 탐색을 이용해 푸는 보글 게임이다 !
문제는 아래와 같다.

보글 게임

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

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

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

입력

입력의 첫 줄에는 테스트 케이스의 수 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

해당 문제는 [알고리즘
문제 해결 전략]의 무식하게 풀기 파트에서 나오는 첫 문제이다.
무식하게 풀기라는 제목처럼 가능한 모든 경우의 수를 탐색하는 완전 탐색 기법을 사용해서 해결할 수 있는 문제이다 !

처음 만난 완전 탐색 문제이니 만큼 책의 풀이를 한번보고 주석을 작성한 후에 코드를 적어내려갔다.

문제 풀이

간단한 방법은 완전 탐색을 이용해 단어를 찾아낼 때까지 모든 인접한 칸을 하나씩 시도해 보는 것이다

주어진 문자의 첫 글자가 보드판 어디에도 존재하지 않으면 당연히 NO를 출력해야한다 !
➡️ 때문에 주어진 글자의 첫 글자가 보드판 존재하는지부터 검사하면서 문제풀이가 시작된다.

주어진 문자의 첫글자를 보드판에서 찾았다면, 그 다음 글자를 찾은 보드판 위치와 맞닿은 곳에서 찾으면 된다. 여기서 똑같은 작업이 반복된다는 것을 쉽게 알 수 있을 것이다 !

주어진 단어의 첫 글자가 보드판 위에 존재하는지

보드판 위에 존재한다면 그 다음에는, 주어진 단어의 첫 글자를 뺀 나머지 단어가 그 인근에 있는지 확인하는 것이다. 이렇게 작은 동일한 작업으로 쪼개질 수 있는 문제는 "재귀"를 이용해 완전 탐색으로 풀 수 있다 !

그렇다면 언제 재귀 함수를 빠져나갈 수 있을까 ?
1. 해당 위치에 있는 글자가 주어진 단어의 첫 글자가 아닌 경우 항상 실패
2. 1번 경우에 해당하지 않을 경우, 원하는 단어가 한 글자인 경우라면 항상 성공 !

위 두 조건간의 순서는 절대 바뀌면 안된다 !
그 이유는 순서를 바꿔보고 직접 디버깅 해보자 :)

코드

책의 설명을 참고하여 작성한 코드는 아래와 같다

#include <iostream>
#include <vector>
#include <string>
using namespace std;

// 맵 이동을 위한 direction vector
const vector<int> dX = {-1, -1, -1, 0 ,0, 1, 1, 1};
const vector<int> dY = {1, 0, -1, 1, -1, 1, 0, -1};

vector< string > mapp(5, "-----");


bool hasWord(int, int, const string &);

int main() {
    // 맵 사이즈 입력 받기
    int testcase;
    cin >> testcase;


    while (testcase--) {

        // 게임 맵 입력받기
        for(int i=0; i<5; i++){
            cin >> mapp[i];
        }


        int cnt;
        cin >> cnt;

        for (int i = 0; i < cnt; i++) {
            string word;
            cin >> word;
            cout << word << " ";
            bool exist = false;
            for (int r = 0; r < 5; r++) {
                for (int c = 0; c < 5; c++) {
                    if (mapp[r][c] == word[0]) {
                        if (hasWord(r, c, word)) {
                            exist = true;
                        }
                    }
                }
            }
            if (exist)
                cout << "YES" << endl;
            else
                cout << "NO" << endl;
        }

    }
    return 0;
}

bool hasWord(int y, int x, const string& word){

    // base case 1: 시작 위치가 게임 맵 범위 밖이면 실패
    if (y < 0 || y >= 5 || x < 0 || x >= 5)
        return false;

    // base case 2: 첫 글자가 일치하지 않으면 실패
    if (mapp[y][x] != word[0])
        return false;

    // base case 3: 단어 길이가 1이면 성공
    if (word.size() == 1)
        return true;

    // 인접한 8칸 검사하기
    for (int direction=0; direction<8; direction++){
        int nextY = y + dY[direction];
        int nextX = x + dX[direction];
        // 다음 칸이 범위 안에 있는지, 첫글자는 일치하는지 확인할 필요 없음 (기저사례에 존재)
        if (hasWord(nextY, nextX, word.substr(1))){
            return true;
        }
    }
    return false;
}

답은 맞았지만, 채점해보면 시간 초과 가 뜬다.
당연히 완전 탐색을 이용해 풀었기 때문에 제한 시간이 여유롭지 않다면 당연한 결과이다.

다음에는 DP(동적 프로그래밍)을 활용하여 이를 빠르게 풀 수 있는 방법을 시도해보자 !


문제 출처 : https://www.algospot.com/judge/problem/read/BOGGLE

profile
잠자면서 돈버는 그날까지

0개의 댓글