알고리즘 문제해결 전략 Chapter 06 - BOGGLE(C++)

포타토·2019년 12월 18일
0

알고리즘

목록 보기
5/76

예제: 보글 게임

문제

보글(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문을 비워버리리라😬

profile
개발자 성장일기

0개의 댓글