[알고리즘][완전 탐색] 보글 게임 알고리즘

1. 보글 게임 알고리즘

일명 무식하게 풀기라는 완전탐색 알고리즘에 대해 알아보겠다.

모든 경우의 수를 다 생각해보자는 것이다. 제대로 이름 값 하는 놈이라 할 수 있다.

이 알고리즘에서는 (앞으로도 계속일테지만) 재귀 호출이 알고리즘에서 상당히 효율적으로 쓰이게 된다.

들어가기에 앞서 간단한 재귀 호출에 대해서 복습을 하고 가자!!

너무나도 간단한 예제이다.

함수 내에서 자기자신을 호출하고 있다.

위의 경우 for문을 써도 간단하게 해결되는 문제지만

문제의 특성에 따라 적절하게 사용한다면

코딩을 훨씬 간단하게 만들 수 있다.

재귀에 대해 어렴풋이 생각이 났다면 바로 들어가보자.

대충 문제 설명

5X5 보드판에 알파벳이 채워져 있고

1. 시작 위치 (x,y) 와 보드판에서 찾을 단어를 입력한다. (ex. word)

2. 시작 위치부터 해서 상하좌우 대각선까지 인접한 부분으로 다음 단어를 찾게 된다.

3. 한 글자가 두번 사용되어 질 수도 있다.

ex)

q w e r d

p m o f t

b w e a n

y w q s s

h m o c c

-->> 좌표 입력 : 1 0

-->> 찾을 단어 : worord

-->> 단어를 찾았습니다. 

string name("abcdefg");

name.strsub(1);                -->bcdefg   --> 매개변수를 하나 전달하면 그 놈만 빼고 (왜 첫 글자가 1이지?)

name.strsub(0,2);           --> abc        --> 매개변수를 두개 전달하면 그 범위에 있는 놈만 살아남는다.

위의 경우에서 

1번. bool hasWord(int, int, string&);    

2번. bool hasWord(int, int, string);

3번. bool hasWord(int, int, const string&);

hasWord( ....  , _word.substr(1));

2번, 3번은 실행이 되는데 1번이 실행이 안됨.

왜 그런건지 꼭 찾아봐야함!