예제: 보글 게임
문제
보글(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풀이
브루트 포스인 척 하는 동적 계획법 문제이다.
워낙 알고리즘 문제해결 전략 책이 어렵다보니, 오히려 이 문제는 수월하게 느껴질 정도였다(머쓱).
사실 책이 너무 어려워서 다시 차근차근 풀고, 포스팅 못했던 문제도 올릴겸 해서 다시 풀고있다.
잡설이 길었고, 이 문제는 한 지점에서 총 8방향으로 움직여 주면서, 내가 찾는 단어가 나오는지 탐색하면 된다. 하나라도 단어를 찾을 경우 return해준다.
필자는 동적 프로그래밍을 하기 위한 cache를 cache[cnt][y][x] 즉 이동 횟수와 y, x좌표를 사용하였다.
이런 유형의 문제가 그런듯 하지만 역시 재귀함수를 사용하였다.
전체적인 소스코드는 아래와 같다.
소스 코드
#include<iostream>
#include<string>
#include<cstring>
using namespace std;
char map[5][5];
string words[10];
int cache[10][5][5];
int N;
//12시부터 시계방향으로
int dy[8] = { -1, -1, 0, 1, 1, 1, 0, -1 };
int dx[8] = { 0, 1, 1, 1, 0, -1, -1, -1 };
int findWord(const string& word, int y, int x, int cnt) {
if (y < 0 || y >= 5 || x < 0 || x >= 5) return 0;
if (word.size() == 1) return word[0] == map[y][x];
int& res = cache[cnt][y][x];
if (res != -1) return res;
if (word[0] != map[y][x]) return res = 0;
for (int i = 0; i < 8; i++) {
if (res = findWord(word.substr(1), y + dy[i], x + dx[i], cnt + 1)) return res;
}
return res;
}
int main() {
int testCase;
cin >> testCase;
for (int tc = 0; tc < testCase; tc++) {
for (int i = 0; i < 5; i++) {
for (int j = 0; j < 5; j++) {
cin >> map[i][j];
}
}
cin >> N;
for (int i = 0; i < N; i++) {
cin >> words[i];
}
for (int i = 0; i < N; i++) {
memset(cache, -1, sizeof(cache));
int flag;
for (int y = 0; y < 5; y++) {
flag = 0;
for (int x = 0; x < 5; x++) {
if (flag = findWord(words[i], y, x, 0)) break;
}
if (flag) break;
}
cout << words[i] << " " << (flag ? "YES" : "NO") << endl;
}
}
return 0;
}풀이 후기
필자는 findWord 함수를 맵 위의 한 위치 (y, x) 에서만 시작하였기 때문에, main문에서 2중 for문을 사용하여 좌표 하나씩 순회하였다.
필자는 main문이 짧은 것이 좋다. 언젠간 main문을 비워버리리라😬
