Life Engineering
[BOJ 9202] Boggle (C++) 본문
https://www.acmicpc.net/problem/9202
Trie 와 DFS 를 응용한 문제
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
|
#include <bits/stdc++.h>
using namespace std;
class Node{
public:
Node* children[26];
bool isEnd;
bool isHit;
Node(){
isEnd=false;
isHit=false;
}
void clearHit(){
isHit=false;
for (int i=0; i<26; i++){
if (children[i]!=NULL){
children[i]->clearHit();
}
}
}
~Node(){
for (int i=0; i<26; i++){
delete children[i];
}
}
};
Node* root=new Node();
string sword, answer;
int dy[8]={ -1, 1, 0, 0, -1, 1, -1, 1 };
int dx[8]={ 0, 0, -1, 1, -1, -1, 1, 1 };
bool visited[4][4];
int scores[9]={0,0,0,1,1,2,3,5,11};
int cnt, sum;
void insert(string word){
Node* current=root;
for (int i=0; i<word.length(); i++){
int wordIndex=word[i]-'A';
if (current->children[wordIndex]==NULL){
current->children[wordIndex]=new Node();
}
current=current->children[wordIndex];
}
current->isEnd=true;
}
string compare(string sword, string answer){
vector<string> v;
v.push_back(sword); v.push_back(answer);
if (sword.length() == answer.length()){
sort(v.begin(), v.end());
return v[0];
}
else if (sword.length()>answer.length()){
return sword;
}
else{
return answer;
}
}
void search(int y, int x, int length, Node* node, string board[]){
visited[y][x]=true; //체크인
sword.push_back(board[y][x]);
int nx, ny;
if (node->isEnd && node->isHit==false){ //목적지인가
node->isHit=true;
sum+=scores[length]; //점수
cnt+=1; //개수
answer=compare(sword, answer);
}
//순회
for (int i=0; i<8; i++){
nx=x+dx[i];
ny=y+dy[i];
char cc=board[ny][nx];
if (nx<0 || ny<0 || nx>=4 || ny>=4){
continue;
}
if (!visited[ny][nx] && node->children[cc-'A']!=NULL){
search(ny, nx, length+1, node->children[cc-'A'],board);
}
}
visited[y][x]=false; //체크아웃
sword.pop_back();
}
void initialize(bool visited[4][4]){
for (int i=0; i<4; i++){
for (int j=0; j<4; j++){
visited[i][j]=false;
}
}
}
int main(){
int w, b;
cin>>w;
string words[w];
string s;
string board[4];
char n[5];
initialize(visited);
for (int i=0; i<w; i++){
cin>>s;
words[i]=s;
}
cin.getline(n, 20);
for (int i=0; i<w; i++){ //tree 구성
insert(words[i]);
}
cin>>b;
for (int i=0; i<b; i++){
sum=0;
cnt=0;
answer="";
for (int j=0; j<4; j++){
cin>>s;
board[j]=s;
}
for (int y=0; y<4; y++){
for (int x=0; x<4; x++){
if (root->children[board[y][x]-'A']!=NULL){
search(y,x,1,root->children[board[y][x]-'A'],board);
}
}
}
cout<<sum<<" "<<answer<<" "<<cnt<<"\n";
initialize(visited);
root->clearHit();
if (i!=b-1){
cin.getline(n, 20);
}
}
delete root;
}
|
cs |
'Problem Solving' 카테고리의 다른 글
[BOJ 1976] 여행 가자(C++) (0) | 2021.08.10 |
---|---|
[BOJ 1261] 알고스팟 (C++) (0) | 2021.08.09 |
[BOJ 1202] 보석 도둑(C++) (0) | 2021.07.22 |
[BOJ 1927] 최소 힙(C++) (0) | 2021.07.22 |
[BOJ 3055] 탈출 (C++) (0) | 2021.07.20 |