06 - 보글 게임 (BOGGLE)

1. 주어진 칸에서 시작해서 특정 단어를 찾을 수 있는지 확인하는 문제. 

 시작점(y,x), 단어(word)를 주겠다는 것 예상

 

2. (y,x) 에서 8방향 탐색(갔던 곳을 다시 갈 수도 있으니 dfs라고 보긴 힘들듯)

 

3.

기저사례

-(y,x)에 있는 글자가 원하는 단어의 첫 글자가 아닌 경우 실패

-원하는 단어가 한 글자인 경우 성공

 

포인트

-매 탐색마다 글자의 맨 앞글자에만 의미 부여

 

4. 시간복잡도는 word의 길이 n에 대해 O(8^n) 

 

5.

bool hasWord(y,x,word) 형태의 재귀적 탐색

   if board[y][x] != word[0] -> return false;

   if word.size() == 1        -> return true;

   for(int dir=0; dir<8; dir++){

      int ny = y+dy[dir], nx = x+dx[dir];

      if(ny>5 || nx>5 || ny<0 || nx<0) continue;   //책에선 이부분을 기저 사례로 하면 코드가 간결해 진다고 함.

      if(hasWord(ny, nx, word.substr(1))

   }

   return false;

 

6. 책에서 말한대로 재귀함수 호출 시 범위 체크를 기저사례에서 해주도록 하자