문제 : www.acmicpc.net/problem/9202
Sort Backtracking BinarySearch
[ 알고리즘풀이 ]
-Sorting
1) 단어사전을 입력받고 sort를 진행한다. ( binary search 를 위해 )
-Backtracking
2) 4 x 4 보드 판을 입력받고, 모든 지점에서 만들 수 있는 모든 단어를 Backtracking 을 이용해서 만든다.
-BinarySearch
3) 만들어진 단어가 단어사전에 있는지 binary search를 이용해 탐색한다.
4) 이진탐색 결과가 실패라면 넘어가고, 성공이라면 가장 긴 단어와 score, 단어 count를 갱신한다.
이때, 같은 단어를 만들어서 찾은 경우라면 한 번만 count 해야 되므로 isSelected bool 배열을 이용해 단어 사전에서 탐색에 성공한 단어들은 체크해둔다.
5) (2) ~ (4) 과정을 보드판마다 반복한다.
[ 코드구현 C++ ]
|
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
|
#include<iostream>
#include<vector>
#include<string>
#include<algorithm>
#include<cstring>
using namespace std;
int w, b;
int scores[9] = { 0, 0, 0, 1, 1, 2, 3, 5, 11 };
int dx[8] = { -1, -1, -1, 0, 1, 1, 1, 0 }, dy[8] = { -1, 0, 1, 1, 1, 0, -1, -1 };
string dictionary[300000];
int cnt, score;
bool isSelected[300000];
bool visited[4][4];
string board[4];
string longWord;
bool isInside(int x, int y) {
return (0 <= x && x < 4 && 0 <= y && y < 4);
}
int binary_search(string word) {
int left = 0, right = w - 1;
while (left <= right) {
int mid = (left + right) / 2;
if (dictionary[mid] == word) return mid;
else if (dictionary[mid] < word) left = mid + 1;
else right = mid - 1;
}
return -1;
}
void makeWord(int x, int y, string word) {
if (int(word.length()) >= 9) return;
if (word.length() >= 1) {
// binarySearch로 찾기
int ind = binary_search(word);
if (ind != -1) {
if (word.length() > longWord.length()) longWord = word;
else if (word.length() == longWord.length() && word < longWord) longWord = word;
if (!isSelected[ind]) {
isSelected[ind] = 1;
cnt++;
score += scores[word.length()];
}
}
}
for (int i = 0; i < 8; i++) {
int nextX = x + dx[i], nextY = y + dy[i];
if (!isInside(nextX, nextY)) continue;
if (visited[nextX][nextY]) continue;
visited[nextX][nextY] = 1;
word.push_back(board[nextX][nextY]);
makeWord(nextX, nextY, word);
word.pop_back();
visited[nextX][nextY] = 0;
}
}
int main(void) {
ios::sync_with_stdio(false);
cin.tie(0); cout.tie(0);
cin >> w;
for (int i = 0; i < w; i++)
cin >> dictionary[i];
sort(dictionary, dictionary + w);
cin >> b;
for (int i = 0; i < b; i++) {
for (int j = 0; j < 4; j++)
cin >> board[j];
memset(isSelected, 0, sizeof(isSelected));
longWord = "";
cnt = 0;
score = 0;
string word;
for (int j = 0; j < 4; j++)
for (int k = 0; k < 4; k++){
word.push_back(board[j][k]);
visited[j][k] = 1;
makeWord(j, k, word);
visited[j][k] = 0;
word.pop_back();
}
cout << score << ' ' << longWord << ' ' << cnt << '\n';
}
}
|
cs |
[ github ]
github.com/travelbeeee/ProblemSolving/blob/master/BOJ/BOJ9202.cpp
travelbeeee/ProblemSolving
백준 문제풀이. Contribute to travelbeeee/ProblemSolving development by creating an account on GitHub.
github.com
'Problem Solving > BOJ' 카테고리의 다른 글
| [BOJ] 1747 : 소수 & 팰린드롬 (0) | 2020.09.18 |
|---|---|
| [BOJ] 14226 : 이모티콘 (0) | 2020.09.15 |
| [BOJ] 1107 : 리모컨 고치기 (0) | 2020.09.14 |
| [BOJ] 17404 : RGB거리 2 (0) | 2020.09.03 |
| [BOJ] 9576 : 책 나눠주기 (0) | 2020.09.02 |