BOJ : https://www.acmicpc.net/problem/9202
github : https://github.com/junho0956/Algorithm/blob/master/9202/9202/%EC%86%8C%EC%8A%A4.cpp
2가지 방법으로 해결했습니다.
trie 자료구조 복습겸 작성해봤고, trie 없이 dfs 하는 방식으로 해봤습니다.
trie 자료구조를 이용한 방법
|
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
|
//Boggle
//일반적인 DFS 문제인데 현재 탐색을 기준 문자열이 존재하는지 없는지 확인하는 작업이 필요하다
//DFS의 탐색때 마다 모든 문자열을 확인 작업하게되면 TLE가 될 것이다
//문자열을 빠르게 찾기 위해서는 수업시간에 배운 trie 자료구조를 사용해야한다.
//문자트리 라고 생각하면 된다
#include <fstream>
#include <iostream>
#include <string>
#include <cstring>
#include <set>
using namespace std;
ifstream fcin("large_hand.in");
ofstream fcout("large_hand.out");
int w, b;
int visit[4][4];
string board[4];
set<string> key;
int score[9] = { 0,0,0,1,1,2,3,5,11 };
int my[8] = { -1,-1,-1,0,0,1,1,1 };
int mx[8] = { -1,0,1,-1,1,-1,0,1 };
struct trie {
// 알파벳A~Z까지에 대한 배열
trie* node[26];
// 단어의 종료를 알리는 배열
bool finish;
// new 를 위한 생성자
trie() {
memset(this->node, NULL, sizeof(this->node));
this->finish = false;
}
// 스트링에 대한 트라이트리 만들기
// 현재 포인터에 대한 다음 포인터가 없다면 연결을 위해 만들어준다
void insert(string s) {
trie* p = this;
for (int i = 0; i < s.length(); i++) {
int index = s[i] - 'A';
if (p->node[index] == NULL)
p->node[index] = new trie();
p = p->node[index];
}
// 단어의 종료를 알려줘야한다
p->finish = true;
}
void search(int y, int x, string s) {
// 단어가 8글자이하라고 했다
if (s.length() > 8) return;
visit[y][x] = 1;
s += board[y][x];
trie* check = this->node[board[y][x] - 'A'];
// 현재 포인터에 대해 방금 추가한 단어가 없다 -> 연결안되있다면 반환
if (check == NULL) {
visit[y][x] = 0;
return;
}
// 중복처리를 위해 set 처리
for (int i = 0; i < 8; i++) {
int yy = y + my[i];
int xx = x + mx[i];
if (yy >= 0 && yy < 4 && xx >= 0 && xx < 4 && visit[yy][xx] == 0) {
check->search(yy, xx, s);
}
}
// dfs 에 의한 방문처리
visit[y][x] = 0;
}
};
int main() {
// trie의 루트노드
trie* root = new trie();
fcin >> w;
while (w--) {
string str;
fcin >> str;
// 단어추가
root->insert(str);
}
fcin >> b;
while (b--) {
for (int i = 0; i < 4; i++)
fcin >> board[i];
// 0.0 부터 3.3 까지 전부 탐색해준다
for (int i = 0; i < 4; i++)
for (int j = 0; j < 4; j++)
root->search(i, j, "");
string longstr = "";
int total = 0, findNum = key.size();
for (string po : key) {
longstr = longstr < po ? longstr : po;
longstr = po;
}
fcout << total << " " << longstr << " " << findNum << "\n";
}
return 0;
}
http://colorscripter.com/info#e" target="_blank" style="color:#e5e5e5text-decoration:none">Colored by Color Scripter
|
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
|
#include <iostream>
#include <set>
#include <vector>
#include <string>
#include <algorithm>
using namespace std;
int w, b;
string board[4];
bool visit[4][4], isFind;
string isWant;
set<string> key;
int score[9] = { 0,0,0,1,1,2,3,5,11 };
int my[8] = { -1,-1,-1,0,0,1,1,1 };
int mx[8] = { -1,0,1,-1,1,-1,0,1 };
string v[300001];
void search(int y, int x, int index) {
if (isFind || index >= isWant.size()) return;
if (isWant[index] != board[y][x]) return;
visit[y][x] = true;
if (index == isWant.size() - 1 && board[y][x] == isWant[index]) {
isFind = true;
visit[y][x] = false;
return;
}
for (int i = 0; i < 8; i++) {
int yy = y + my[i];
int xx = x + mx[i];
if (yy >= 0 && yy < 4 && xx >= 0 && xx < 4 && visit[yy][xx] == 0) {
search(yy, xx, index + 1);
if (isFind) {
visit[y][x] = false;
return;
}
}
}
visit[y][x] = false;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(NULL); cout.tie(NULL);
cin >> w;
for (int i = 0; i < w; i++) cin >> v[i];
cin >> b;
while (b--) {
for (int i = 0; i < 4; i++)
cin >> board[i];
for (int k = 0; k < w; k++) {
bool t = false;
for (int i = 0; i < 4; i++) {
for (int j = 0; j < 4; j++) {
if (board[i][j] == v[k][0]) {
isFind = false;
isWant = v[k];
int num = key.size();
search(i, j, 0);
if (num != key.size()) { t = true; break; }
}
}
if (t) break;
}
}
string longest = "";
int total = 0, cnt = key.size();
for (string at : key) {
longest = longest < at ? longest : at;
longest = at;
}
cout << total << " " << longest << " " << cnt << "\n";
}
}
http://colorscripter.com/info#e" target="_blank" style="color:#e5e5e5text-decoration:none">Colored by Color Scripter
|
'algorithm > BOJ' 카테고리의 다른 글
| BOJ 15922번 아우으 우아으이야!! (0) | 2020.02.05 |
|---|---|
| BOJ 2170번 선 긋기 (0) | 2020.02.05 |
| BOJ 10999번 구간 합 구하기2 (0) | 2020.02.05 |
| BOJ 2042번 구간 합 구하기 (0) | 2020.02.05 |
| BOJ 3055번 탈출 (0) | 2020.02.04 |