알고스팟 : BOGGLE

링크 : https://algospot.com/judge/problem/read/BOGGLE

상하좌우, 대각선으로 접근할 수 있다. 게다가 중복해서 가져올 수 있다는 점도 잊으면 안된다. 게다가 지금 배우는 6장의 코드는 너무 느리다고 사이트에 언급이 되어있다.

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

문제의 분할

hasWord()를 통해 각 글자를 하나씩 조각낸다. word의 각 자리 수가 격자안에 존재하면 true를, 존재하지 않는다면 false를 도출한다.

기저 사례의 선택

1. 위치 (y, x)에 있는 글자가 원하는 단어의 첫 글자가 아닌 경우 항상 false
2. (1번 경우에 해당하지 않을 경우, true가 나온 경우) 원하는 단어가 한글자인 경우 항상 성공

위 2가지를 순서에 맞춰 진행한다.

입력이 잘못되거나 범위에서 벗어난 경우도 기저 사례로 택하여 맨 처음에 처리하는 것을 통해 함수를 호출하는 시점에서 이러한 오류를 검사하지 않도록 만든다.
재귀 함수는 항상 한군데 이상에서 호출되기 때문에 쓸데없는 case를 제거하는 것이 성능에 좋다.
따라서 격자의 위치에서 벗어난 경우와 첫 글자가 일치하지 않는 경우를 모두 기저 사례로 선택해서 처리해야 한다.

구현

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

char table[5][5];
const int dx[8]{ -1,-1,-1,1,1,1,0,0 };
const int dy[8]{ -1,0,1,-1,0,1,-1,1 };

bool isRange(int x, int y) {
	return (-1 < x && x < 5 && -1 < y && y < 5);
}

bool hasWord(int x, int y, const string& word) {
	//base case : 범위에서 벗어날 경우
	if (!isRange(x, y)) return false;
	//base case : 첫 글자가 시작 글자와 다른 경우
	if (table[x][y] != word[0]) return false;
	//base case : 첫 글자를 찾고 그 글자의 길이가 1일 경우
	if (word.size() == 1) return true;

	for (int i = 0; i < 8; i++) {
		int nextX = x + dx[i];
		int nextY = y + dy[i];
		if (hasWord(nextX, nextY, word.substr(1)))
			return true;
	}
	return false;
}

void search(const string& word) {
	for (int i = 0; i < 5; i++) {
		for (int j = 0; j < 5; j++) {
			if (hasWord(i, j, word)) {
				cout << word << " YES" << endl;
				return;
			}
		}
	}

	cout << word << " NO" << endl;
	return;
}

int main() {
	int tcase;
	char apb;
	cin >> tcase;
	for (int i = 0; i < 5; i++) {
		for (int j = 0; j < 5; j++) {
			cin >> table[i][j];
		}
	}
	
	cin >> tcase;
	string word;
	
	for (int i = 0; i < tcase; i++) {
		cin >> word;
		search(word);
	}
	return 0;
}

우선 시간 초과 나온다.
구현은 대략적으로 잘 접근했는데 for문의 반복과 재귀가 시간 초과를 불러일으킨게 아닐까 싶다. 8장 끝나고 다시 보자.