[algospot] BOGGLE

보글 게임 (ID : BOGGLE 下) 

---

내 풀이 코드

#include <iostream>
#include <string>
#include <fstream>

using namespace std;

bool inRange(int x, int y){
	if(x < 0 || x > 4 || y < 0 || y > 4) {
		return false;
	}
	return true;
}
bool boggle(int x, int y, const string &knownWord, string table[]){
	int gridX[3] = { -1, 0, 1};
	int gridY[3] = { -1, 0, 1};

	// 기저사례 설정
	
	// 1. 범위를 벗어나면 탈락
	if(!inRange(x, y)) {
		return false;
	}
	
	// 2. 첫 글자가 일치하지 않으면 실패
	if(table[x][y] != knownWord[0]){
		return false;
	}
	cout << "x : " << x << " y : " << y << " knownWord : " << knownWord << endl;

	// 3.단어 길이가 1이면 성공
	if(knownWord.size() == 1) {
		return true;
	}
	
	// 인접 칸을 돈다.
	for(int i = 0; i < 3; i++){
		for(int j = 0; j < 3; j++){
			int nextX = x + gridX[i], nextY = y + gridY[j];
			if(i == 1 && j == 1){ // 제자리는 건너뜀
				continue;
			}
			if(boggle(nextX, nextY, knownWord.substr(1), table)) //
				return true;
		}
	}
	return false;
}

int main(){
	int C, knownNum;
	string table[5];
	string knownWords[10];
	bool isExist[10] = {false};
	
	// 파일 입출력을 위함.
	std::ifstream readFile;
	readFile.open("./boggle.txt");
	
	readFile >> C; // cin >> C;
	readFile.ignore(); // cin.ignore();

	for(int c = 0; c < C; c++){
		for(int i = 0; i < 5; i++){
			getline(readFile, table[i]); // getline(cin, table[i]);
		}
		readFile >> knownNum; // cin >> knownNum;
		readFile.ignore(); // cin.ignore();


		for(int i = 0; i < knownNum; i++){
			getline(readFile, knownWords[i]); // getline(cin, knownWords[i]);
		}

		for(int i = 0; i < knownNum; i++){
	
			for(int x = 0; x < 5; x++){
				for(int y = 0; y < 5; y++){
					
					if(!isExist[i] && table[x][y] == knownWords[i][0]){
						cout << endl;
						isExist[i] = boggle(x, y, knownWords[i], table);				
					}
				}
			}
		}

		for(int i = 0; i < knownNum; i++){
			cout << endl;
			cout << knownWords[i] << (isExist[i] ? " YES" : " NO") << endl;
		}
	}
}

문제의 간단한 해법

어떠한 방식 / 깨달음 으로 접근했는지 & 사용한 문제 해결 전략

 

재귀 함수에 돌입하기 전, 첫머리글자가 있는 곳을 찾아내어서 재귀 함수에 준다.

이후의 작업은 재귀 함수에서 돌며, 인접한 8칸 모두를 탐색하는 방식이었다. 만약 인접한 칸 중 다음 글자와 일치하는 칸이 있으면 현재 string 에서 해당 글자를 빼고 재귀한다.

단순한 방식으로 풀어보기

오답 원인

- cin.ignore() 버퍼 클리어 를 이용해서 getline 의 개행 문자 먹는 실수를 없앴다. 이 실수는 파일 출력을 할 때에도 발생하였는데 ifstream 의 ignore() 을 사용하면 같은 버퍼 클리어 효과를 낼 수 있었다.

- 전형적인 i j 구분 못하는 오타를 냈어서 segmentation fault 를 발생시켰다. 컴파일러가 잡아주지 못하는 이러한 사소한 오류를 하지 말자.

- 또 다른 상수 오타였다. gridX 와 gridY 를 선언해두고 제자리를 빙빙 도는 기존의 x + 0 기존의 y + 0 을 건너뛰기 위해서 39 줄의 조건문을 추가한 것인데 i, j 와 gridX[i], gridY[j] 를 헷갈려서 0 과 1 을 헷갈린.. 결국 상수 오타였다.

- 여러 개의 시작점이 있을 때, 앞선 시작점에선 true 이고 뒤의 시작점에선 false 일 때 문제가 발생하였다. 그래서, isExist 의 해당 인덱스가 true 가 된다면 재귀 함수 boggle 을 들어가지 않기로 했다.

새로이 배운 점

- c++ string 클래스 사용

- 예제 코드를 콘솔 창에 일일히 쳐서 테스트를 돌려보는 것은 지치고 매우 비효율적이며 능률이 없는 작업이라고 생각하여 아예 예제 코드를 텍스트 파일로 만들어서 파일 입출력 형식으로 테스트를 돌려보기로 하였다. 이렇게 하였더니 검증하는 속도가 매우 빨라졌으며 효율적이게 되었다. 이번에는 파일 출력 에 관해서만 사용했으나 나중에는 더 나아가서 file io 을 더 공부해보자.

- 중복 검증을 피하기 위해서 입력이 잘못되거나 범위에서 벗어난 경우도 기저 사례로 택해서 맨 처음에 처리하는 것 이 인상 깊었다.

다른 사람(책)의 코드를 보고 비교

다음 글자가 될 수 있는 칸이 여러 개 일때, 어느 글자를 선택해야 할지 미리 알 수 없으므로, 완전 탐색을 활용하여 단어를 찾아낼 때 까지 모든 인접한 칸을 돌아본다.

 더 이상의 탐색 없이 간단히 답을 낼 수 있는 다음 경우들을 기저 사례로 선택하였다.

1. 위치 (x, y) 에 있는 글자가 원하는 단어의 첫 글자가 아닌 경우 항상 실패

2. (1번이 아닌 경우) 원하는 단어가 한 글자인 경우 항상 성공