백준 11521번 Boggle

문제 링크입니다: https://www.acmicpc.net/problem/11521

종만북을 공부하다가 알고스팟 BOGGLE(http://jaimemin.tistory.com/300) 문제와 유사한 문제가 있어서 풀어봤습니다.

알고리즘은 아래와 같습니다.

1. 모든 칸을 순회하며 i 번째 단어의 첫 번째 문자와 같은 곳에서부터 재귀함수를 호출합니다.

i) 해당 칸이 q라면 qu로 처리해야하기 때문에 i 번째 단어가 qu로 시작하는지 확인해야합니다.

2. 인덱스가 해당 단어의 길이가 된다면 보글 보드에서 단어를 찾았다는 의미이므로 true를 반환합니다.(기저 사례)

3. 동서남북 그리고 대각선까지 확인해야하기 때문에 반복문을 8번 돌려 각 방향을 확인합니다.

i) 1번과 마찬가지로 처리하면 됩니다.

ii) 1번과 다르게 다음 문자가 q일 때 조건이 하나 더 생깁니다.

a) 다음 문자가 q라면 q 다음에 u도 반드시 있어야합니다.

b) 따라서, 현재 인덱스가 최대 s.length() - 2여야 합니다.(s.length() - 1 즉, 마지막 인덱스라면 qu가 올 수 없기 때문에 단어를 찾지 못한 것으로 판단합니다.)

4. 결과를 출력할 때는 사전순으로 출력해야하기 때문에 result를 정렬하고 출력합니다.

#include <iostream>

#include <string>

#include <vector>

#include <algorithm>

#include <cstring>

using namespace std;

 

const int MAX = 8;

 

typedef struct

{

        int y, x;

}Dir;

 

Dir moveDir[8] = { {1, 1}, {1, 0}, {1, -1}, {0, 1}, {0, -1}, {-1, 1}, {-1, 0}, {-1, -1} };

 

int W, D;

vector<pair<string, bool>> v; //word, searched?

string board[MAX];

bool visited[MAX][MAX];

 

bool hasWord(int idx, int y, int x, string s) //string의 인덱스, {좌표}, 찾고자 하는 단어

{

        //조건 만족

        if (idx == s.length())

                 return true;

 

        //방문했다고 표시합니다.

        visited[y][x] = true;

        bool flag = false;

        for (int i = 0; i < 8; i++)

        {

                 if (flag)

                         break;

                 int nextY = y + moveDir[i].y;

                 int nextX = x + moveDir[i].x;

 

                 //범위 내에 있고 아직 찾지 못한 단어

                 if (0 <= nextY && nextY < D && 0 <= nextX && nextX < D && !visited[nextY][nextX])

                         //q일 경우 qu로 간주

                         if (board[nextY][nextX] == 'q')

                         {

                                 if (idx < s.length() - 1 && s[idx] == 'q' && s[idx + 1] == 'u')

                                          flag = hasWord(idx + 2, nextY, nextX, s);

                         }

                         else if (board[nextY][nextX] == s[idx])

                                 flag = hasWord(idx + 1, nextY, nextX, s);

        }

        //이 부분이 핵심(다시 방문하지 않았다고 표시)

        visited[y][x] = false;

        return flag;

}

 

int main(void)

{

        ios_base::sync_with_stdio(0);

        cin.tie(0);

        cin >> W;

 

        for (int i = 0; i < W; i++)

        {

                 string temp;

                 cin >> temp;

 

                 v.push_back({ temp, false });

        }

 

        while (1)

        {

                 cin >> D;

                 if (D == 0)

                         break;

 

                 //새로운 판마다 단어들을 다시 찾아보기 떄문에 초기화

                 for (int i = 0; i < W; i++)

                         v[i].second = false;

                

                 for (int i = 0; i < D; i++)

                         cin >> board[i];

 

                 vector<string> result;

                 for (int i = 0; i < W; i++)

                 {

                         for(int j=0; j<D; j++)

                                 for (int k = 0; k < D; k++)

                                 {

                                          bool flag = false;

                                          memset(visited, false, sizeof(visited));

                                          //q로 시작하는 블록은 qu로 간주

                                          if (board[j][k] == 'q')

                                          {

                                                  if (!v[i].second && v[i].first.length() >= 2 && v[i].first[0] == 'q' && v[i].first[1] == 'u')

                                                          flag = hasWord(2, j, k, v[i].first);

                                          }

                                          else if (!v[i].second && board[j][k] == v[i].first[0])

                                                  flag = hasWord(1, j, k, v[i].first);

 

                                          if (flag)

                                          {

                                                  //중복 삽입을 피하기 위해 표시

                                                  v[i].second = true;

                                                  result.push_back(v[i].first);

                                          }

                                 }

                 }

 

                 //알파벳 순서대로 정렬

                 sort(result.begin(), result.end());

                 for (int i = 0; i < result.size(); i++)

                         cout << result[i] << "\n";

                 cout << "-\n";

        }

        return 0;

}

개발환경:Visual Studio 2017

지적, 조언, 질문 환영입니다! 댓글 남겨주세요~

참고: [프로그래밍 대회에서 배우는 알고리즘 문제해결전략]