https://www.acmicpc.net/problem/9202
레벨 : P5
알고리즘 분류 : 자료 구조, 그래프 이론, 문자열, 브루트포스, 그래프 탐색, 트리, 깊이 우선 탐색, 백트래킹, 트라이
접근
DFS를 통해 보드에서 가능한 단어들을 찾고 해당 단어가 사전에 들어있는지를 확인해야한다.
시간 제한이 10초로 넉넉하기는 하지만, 단어 사전에 최대 30만개의 단어가 들어갈 수 있고, 보드의 개수도 30개이기 때문에 매번 선형탐색을 통해 단어가 있는지를 확인한다면 시간이 너무 오래 걸리게 된다.
Trie 자료구조를 이용한다면 보다 빠르게 단어를 탐색할 수 있다.
Code 해제
class Node{}
단어 정보를 저장하기 위해 클래스를 이용해 Trie를 구현했다. 자세한 내용은 이 문서를 읽어보자.
class Node{
public :
int depth = 0;
unordered_map<char, Node*> child;
Node(){}
Node(int d) {
depth = d;
}
void insert(string word, int idx){
if (!word[idx]){
child['*'] = new Node(depth + 1);
return;
}
if (child.count(word[idx])) {
child[word[idx]]->insert(word, idx + 1);
}
else {
child[word[idx]] = new Node(depth + 1);
child[word[idx]]->insert(word, idx + 1);
}
}
bool find(string word, int idx){
if (child.count(word[idx])){
return child[word[idx]]->find(word, idx + 1);
}
if (depth == word.length() && child.count('*')) return true;
return false;
}
};✏️ Field 설명
int depth : 지금이 노드까지 얻을 수 있는 문자열의 길이와 같음.
unordered_map<char, Node*>child : 다음 문자를 값으로 가지는 자식 노드들을 저장.
❓ C++에서의 unorered_map과 map
unordered_map은 해시맵, map은 균형 이진트리의 구조를 가지고 있다.
map의 경우 단어를 삽입, 삭제 할 때 내부적으로 정렬이 일어나기 때문에 unordered_map보다는 느리다. 탐색의 경우에도 map은 , unordered_map은 이 걸린다.
Variables
Node head = Node();
int w, b;
string word, longestWord, result;
set<string> found;
string board[4];
bool visited[4][4];
int dir[8][2] = {{0, 1}, {1, 0}, {-1, 0}, {0, -1}, {1, -1}, {-1, 1}, {1, 1}, {-1, -1}};
int score;Node head : Trie의 head가 될 노드
int w, b : 입력받을 단어 수 w와 보드의 수 b
string word : 입력받을 단어
string longestWord : 보드를 탐색해서 찾아낸 단어 중 가장 긴 단어
set<string> : 찾아낸 단어의 집합
string board[4] : 입력받을 보드
bool visited[4][4] : 보드에서 방문한 곳을 마크하기 위한 배열
int dir[8][2] : 탐색할 수 있는 여덟 방향
int score : 최대 점수
main()
int main(){
cin >> w; //단어의 개수를 입력받고
for (int i = 0; i < w; i++){
cin >> word; //w개의 단어를 입력 받는다.
head.insert(word , 0); //입력받은 단어는 trie에 넣어준다.
}
cin >> b; //보드의 개수를 입력받는다.
for (int i = 0; i < b; i++){
found.clear(); //찾은 단어 집합을 초기화하고
longestWord = ""; //찾은 가장 긴 단어도 초기화하고
score = 0; //점수도 초기화한다.
for (int i = 0; i < 4; i++) cin >> board[i]; //보드를 입력받는다.
for (int i = 0; i < 4; i++){ //보드의 각 문자들에 대해
for (int j = 0; j < 4; j++){
if (!head.child.count(board[i][j]))
continue; //만약 그 문자로 시작하는 단어가 없으면 넘기고
visited[i][j] = true; //나머지 경우에는 dfs를 진행한다.
dfs(head.child[board[i][j]], 1, i, j, board, "");
visited[i][j] = false;
}
}
cout << score << " " << longestWord << " " << found.size() << endl;
//최대 점수, 가장 긴 단어, 찾은 단어의 수를 출력한다.
}
}dfs()
void dfs(Node* node, int length, int x, int y, string board[4], string result){
if (length > 8) return; //단어의 최대 길이가 8이므로 그 이상 탐색할 필요는 없음
string cpy = result + board[x][y]; //이제까지 찾은 단어에 보드의 현재 문자를 붙여본다.
if (head.find(cpy, 0)) { //만약 위 문자열이 사전에 등록된 단어라면?
if (longestWord.length() < cpy.length())
longestWord = cpy; //최장 단어인 경우 갱신
else if (longestWord.length() == cpy.length() && longestWord > cpy)
longestWord = cpy; //길이가 같은 경우, 사전 순서 상 앞서는 경우 갱신
if (found.count(cpy) == 0){ //만약 이제까지 찾은 단어 집합에 속해있지 않다면
found.insert(cpy); //집합에 넣어주고
switch (cpy.length()){ //점수를 추가해 준다.
case 3:
case 4: score += 1; break;
case 5: score += 2; break;
case 6: score += 3; break;
case 7: score += 5; break;
case 8: score += 11; break;
default : break;
}
}
}
for (int i = 0; i < 8; i++){ //8 방향에 대해
int nextX = x + dir[i][0];//다음 위치를 확인한다.
int nextY = y + dir[i][1];
if (nextX < 0 || nextY < 0 || nextX >=4 || nextY >= 4) continue; //범위 밖이거나
if (visited[nextX][nextY]) continue; //이미 방문했거나
char c = board[nextX][nextY];
if (!(node->child.count(c))) continue; //해당 자리가 현재 노드의 child에 없는 경우는 제외
visited[nextX][nextY] = true; //재귀적으로 다시 진행
dfs(node->child[c], length + 1, nextX, nextY, board, cpy);
visited[nextX][nextY] = false;
}
}