Crocodile Tears

보글(Boggle) 게임은 NxM 크기의 알파벳 격자를 가지고 하는 게임인데,

목적은 상하좌우 / 대각선으로 인접한 칸들의 글자들을 이어서 단어를 찾아내는 것입니다.

(테스트를 위해 전체를 검색하여 존재하는지 여부 판단하도록 함)

// 상하좌우/대각선으로 인접한 칸들의 글자들을 이어서 단어를 찾아내는 문제.
/* 예를 들어
Y O S
H E K
Q Z W

인 경우 YES를 찾으면 {0, 0}, {1, 1}, {2, 0}을 순서대로 찾으면 된다.

예제의 경우 특정 위치에서 시작하지 않고, 해당 단어가 있는지 판단만 하도록한다.
*/

#include 
#include 
#include 
using namespace std;

class Boggle
{
public:
	// 게임판 정보
	vector board;

	Boggle()
	{
		// 게임판 세팅
		board.push_back("URLPM");
		board.push_back("XPRET");
		board.push_back("GIAET");
		board.push_back("XTNZY");
		board.push_back("HOQRS");
	}

	// 5x5 게임판에서 주어진 단어가 시작하는지 반환.
	bool hasWord(int x, int y, const string& word)
	{
		// 범위를 넘어가면 실패.
		if (x < 0 || y < 0 || x >= 5 || y >= 5) return false;
		// 단어의 첫번째가 안맞으면 실패;
		if (board[x][y] != word[0]) return false;
		// 단어의 첫번째가 맞았는데 길이가 1이면 성공.
		if (word.size() == 1) return true;
		// 현재 위치 중심으로 주변을 검색한다.
		for (int dx = -1;  dx <= 1; dx++)
		{
			for (int dy = -1; dy <= 1; dy++)
			{
				if (hasWord(x + dx, y + dy, word.substr(1)))
					return true;
			}
		}
		return false;
	}
};

int main()
{
	Boggle boggle;

	string target = "";
	cout << "찾을 문자열 입력" << endl;
	cin >> target;
	bool bFound = false;

	for (int x = 0; x < 5; x++)
	{
		for (int y = 0; y < 5; y++)
		{
			if (boggle.hasWord(x, y, target))
			{
				bFound = true;
				break;
			}
		}

		if (bFound)	break;
	}

	cout << "찾을 문자열 " << target << " 존재 : " << (bFound ? "YES" : "NO") << endl;

	system("pause");
}

< 결과 >

 알고리즘문제해결전략

n개의 원소 중 m개를 고르는 모든 조합을 찾는 알고리즘.

// n개의 원소 중 m개를 고르는 모든 조합을 찾는 알고리즘.

/*
예를 들어 N이 7이면 (0, 1,2, 3), (0, 1, 2, 4), (0,1, 2, 5), ....(3, 4, 5, 6).. 이다.

만약 m이 5개면? for문 5번해야함;; 뭔짓임.
*/

void UseFor(int n)
{
	for (int i = 0; i < n; i++)
	{
		for (int j = i + 1; j < n; j++)
		{
			for (int k = j + 1; k < n; k++)
			{
				for (int l = k + 1; l < n; l++)
				{
					cout << i << " " << j << " " << k << " " << l << endl;
				}
			}
		}
	}
}

/*
n: 전체 원소의 수
picked : 지금까지 고른 원소들의 번호
toPick : 더 고를 원소의 수
*/
void pick(int n, vector& picked, int toPick)
{
	if (toPick == 0)
	{
		for (int nIndex = 0; nIndex < picked.size(); ++nIndex)
		{
			cout << picked[nIndex] << " ";
		}

		cout << endl;
		return;
	}

	// 고를 수 있는 가장 작은 번호를 계산한다.
	int smallest = picked.empty() ? 0 : picked.back() + 1; 

	// 이 단계에서 원소 하나를 고른다.
	for (int next = smallest; next < n; ++next)
	{
		picked.push_back(next);
		pick(n, picked, toPick - 1);
		picked.pop_back();
	}
}

int main()
{
	int n = 10;

	//UseFor(n);

	vector v;
	pick(n, v, 8);

	getchar();

	return 0;
}

[ 결과 ]