336x280(권장), 300x250(권장), 250x250, 200x200 크기의 광고 코드만 넣을 수 있습니다.
보글(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"); }
< 결과 >
알고리즘문제해결전략
'알고리즘' 카테고리의 다른 글
[알고리즘]선택정렬(Selection Sort) (0) | 2016.05.19 |
---|---|
[알고리즘]버블정렬(Bubble Sort) (0) | 2016.05.17 |
[알고리즘]XOR 이용한 교체 알고리즘(swap) (0) | 2016.05.17 |
[알고리즘]n개의 원소에서 m개를 고르는 모든 조합 찾기. (0) | 2015.09.03 |
[알고리즘] 1부터 N까지 합 (0) | 2015.09.03 |