March 31, 2021 ( last updated : March 31, 2021 )
트리에 자료구조 브루트포스 그래프탐색 dfs 알고리즘 algorithm

Abstract

[백준] 9202번 Boggle

알고리즘 유형

자료구조
그래프탐색
트리에
브루트포스

문제 이해

이 문제에서 중요한 점은 하나의 주사위 즉 주어진 한번의 4x4 보드에서 단어 사전의 단어들은 한번 씩만 사용 가능하다는 것이다. 처음에는 보드에서 한 글자를 사용하면 다시 못사용한다는 건줄 알았는데 전혀 다른 말이었다. 이는 첫번째 예제만 세어보아도 알 수 있었다.

풀이방법

dfs까지는 이해했다. 그렇다면 한 글자씩 dfs를 돌아야지 모든 경우의 수를 탐색할 수 있을 것 같았다. 한 보드를 가정했을 때 모든 16글자를 돌아가면서 dfs를 실행하면 되는 것이다.

dfs가 실행 될 때 마다 가지고 있는 글자를 모든 단어사전과 비교하는 과정인것이다. 여기서 가장 오래 걸리는 것은 현재 만든 단어가 단어사전에 있는지 비교하는 것일 것이므로 탐색시간이 적게 걸리는 unordered_map을 통해서 탐색시간을 줄였다.

보드마다 단어 사전은 한번씩만 사용가능하므로 단어마다 31개의 배열을 가지게하여서 단어를 사용했는지 체크하였다. 그리고 단어가 사용안되고 단어사전에 단어가 있다면 vector에 넣어줬다. 이유는 모르겠지만 unordered_set보다 vector가 훨씬 빠르게 나와서 vector에 맞춘 단어를 넣어주고 다시 vector에서 꺼내면서 가장 긴 단어를 찾아낸다.

#include <iostream>
#include <unordered_map>
#include <vector>

#define endl '\n'

using namespace std;

int sc[] = {0, 0, 1, 1, 2, 3, 5, 11};
int dx[] = {-1, 1, 0, 0, 1, 1, -1, -1};
int dy[] = {0, 0, -1, 1, -1, 1, -1, 1};
int is_visited[4][4], W, B, SCORE;
string board[4], longest;
vector<string> boggled;
unordered_map<string, int[31]> WORDS;

// dfs
void search(int y, int x, string s, int t) {
  if (s.length() > 8)
    return;
  if (WORDS[s][30] && !WORDS[s][t]) {
    WORDS[s][t] = true;
    boggled.push_back(s);
  }
  if (is_visited[y][x]) {
    return;
  }
  is_visited[y][x] = 1;
  s.push_back(board[y][x]);

  for (int i = 0; i < 8; i++) {
    int nx = x + dx[i];
    int ny = y + dy[i];
    if (0 > nx || nx > 3 || 0 > ny || ny > 3)
      continue;
    search(ny, nx, s, t);
  }

  s.pop_back();
  is_visited[y][x] = 0;
}

int main() {
  ios::sync_with_stdio(false);
  cin.tie(NULL);
  cout.tie(NULL);

  cin >> W;
  while (W--) {
    string s;
    cin >> s;
    WORDS[s][30] = 1;
  }

  cin >> B;

  while (B--) {

    for (int i = 0; i < 4; i++) {
      cin >> board[i];
    }
    SCORE = 0;
    longest = "";
    boggled.clear();

    for (int i = 0; i < 4; i++) {
      for (int j = 0; j < 4; j++) {
        search(i, j, "", B);
      }
    }
    for (string boggle : boggled) {
      if (boggle.length() > longest.length() ||
          boggle.length() == longest.length() && longest > boggle)
        longest = boggle;
      SCORE += sc[boggle.length() - 1];
    }
    cout << SCORE << ' ' << longest << ' ' << boggled.size() << endl;
  }
  return 0;
}

이렇게도 풀렸지만 많은 사람들은 다른 방법으로 푼 듯하다. 바로 Trie라는 자료 구조를 이용해서이다. 해당 자료 구조는 구글링해보면 간단히 나오면 설명을 생략하겠다.

아무래도 Trie를 이용하면 단어가 될 가능성이 없는 글자로 dfs를 실행하지 않을 수 있게 되고 그로인해서 시간을 대폭 줄일 수 있는 것 같다. 위 코드로는 7000정도 나오는데 Trie를 이용하면 최대 1500까지 시간이 단축되는 것을 볼 수 있었다.

#include <iostream>
#include <set>
#include <vector>

#define endl '\n'

using namespace std;
int sc[] = {0, 0, 1, 1, 2, 3, 5, 11};
int dx[] = {-1, 1, 0, 0, 1, 1, -1, -1};
int dy[] = {0, 0, -1, 1, -1, 1, -1, 1};
int is_visited[4][4], W, B, SCORE;
string board[4], longest;
vector<string> boggled;

class Trie {

public:
Trie \*alp[26];
bool end;
bool visit[30];

~Trie() {
for (int i = 0; i < 26; i++) {
if (alp[i])
delete alp[i];
}
}

void insert(const char *key) {
if (*key == '\0')
end = true;
else {
int cur = \*key - 'A';
if (alp[cur] == NULL)
alp[cur] = new Trie();
alp[cur]->insert(key + 1);
}
}

// dfs
void search(int y, int x, string s, int t) {
if (end && !visit[t]) {
visit[t] = true;
boggled.push_back(s);
}
if (is_visited[y][x])
return;
is_visited[y][x] = 1;
int \_idx = board[y][x] - 'A';
if (alp[_idx]) {
s.push_back(board[y][x]);
for (int i = 0; i < 8; i++) {
int nx = x + dx[i];
int ny = y + dy[i];
if (0 > nx || nx > 3 || 0 > ny || ny > 3)
continue;
alp[_idx]->search(ny, nx, s, t);
}
s.pop_back();

      is_visited[y][x] = 0;
    } else {
      is_visited[y][x] = 0;
      return;
    }

}
};

int main() {
ios::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
Trie \*root = new Trie();

cin >> W;
while (W--) {
char s[10] = {};
cin >> s;
root->insert(s);
}

cin >> B;

while (B--) {

    for (int i = 0; i < 4; i++) {
      cin >> board[i];
    }
    SCORE = 0;
    longest = "";
    boggled.clear();

    for (int i = 0; i < 4; i++) {
      for (int j = 0; j < 4; j++) {
        root->search(i, j, "", B);
      }
    }
    for (string boggle : boggled) {
      if (boggle.length() > longest.length() ||
          boggle.length() == longest.length() && longest > boggle)
        longest = boggle;
      SCORE += sc[boggle.length() - 1];
    }
    cout << SCORE << ' ' << longest << ' ' << boggled.size() << endl;

}
delete root;
return 0;
}

Originally published March 31, 2021
Latest update March 31, 2021

Related posts :

[백준] 9202 Boggle

Abstract

[백준] 9202번 Boggle

알고리즘 유형

문제 이해

풀이방법