9202번: Boggle
각각의 Boggle에 대해, 얻을 수 있는 최대 점수, 가장 긴 단어, 찾은 단어의 개수를 출력한다. 한 Boggle에서 같은 단어를 여러 번 찾은 경우에는 한 번만 찾은 것으로 센다. 가장 긴 단어가 여러 개
www.acmicpc.net
먼저 사전에 들어갈 N개의 단어가 주어지고, 4*4크기의 그리드가 주어집니다.
이 그리드에서 가로, 세로, 대각선으로 인접한 글자로 사전의 단어를 몇 개 만들 수 있는지 찾는 문제입니다.
출력해야 할 것은 게임에서 얻을 수 있는 최대 점수, 찾은 단어 중 가장 긴 단어, 찾은 단어의 갯수 입니다.
저는 사전의 단어를 dfs로 하나씩 확인하였습니다.
(1,1) -> (1,2) -> (1,1)와 같은 중복방문이 없어야하므로 visit를 이용해 방문체크를 하였고,
한 인덱스에서 단어찾기에 실패하면 그 인덱스의 방문처리는 false로 하여 재방문 할 수 있게 하였습니다.
단어 찾는데 성공하면 가장 긴 단어를 최신화하고, 단어 길이에 맞는 점수 증가와 단어 갯수를 1 증가시킵니다.
그리고 같은 단어를 여러번 찾을 필요가 없으므로 찾았다는 표시로 chk = true를 해서 다음 단어로 바로 넘어갑니다.
가장 긴 단어를 출력할 때는 길이가 긴 것, 길이가 같으면 사전 순으로 앞서는 것을 출력합니다.
|
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
|
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
public class Main {
static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
static StringTokenizer st;
static StringBuffer sb = new StringBuffer();
static int direct[][] = { { 0, 1 }, { 1, 1 }, { 1, 0 }, { 1, -1 }, { 0, -1 }, { -1, -1 }, { -1, 0 }, { -1, 1 } };
static int score[] = { 0, 0, 0, 1, 1, 2, 3, 5, 11 };
static String dict[];
static char list[][];
static boolean visit[][], chk;
static String maxlength = "";
static int N, M, maxscore, ans;
static void dfs(int k, int idx, int x, int y) {
if (idx + 1 == dict[k].length()) {
if (maxlength == "")
maxlength = dict[k];
else {
if (maxlength.length() < dict[k].length())
maxlength = dict[k];
else if (maxlength.length() == dict[k].length()) {
if (maxlength.compareTo(dict[k]) > 0)
maxlength = dict[k];
}
}
maxscore += score[idx + 1];
chk = true;
return;
}
visit[x][y] = true;
for (int i = 0; i < 8; i++) {
int nx = x + direct[i][0];
int ny = y + direct[i][1];
if (nx < 0 || ny < 0 || nx >= 4 || ny >= 4)
continue;
if (visit[nx][ny] || list[nx][ny] != dict[k].charAt(idx + 1))
continue;
dfs(k, idx + 1, nx, ny);
if (chk)
return;
visit[nx][ny] = false;
}
}
static void func() {
for (int k = 0; k < N; k++) {
chk = false;
for (int i = 0; i < 4; i++) {
for (int j = 0; j < 4; j++) {
if (list[i][j] == dict[k].charAt(0)) {
visit = new boolean[4][4];
dfs(k, 0, i, j);
if (chk) {
ans++;
break;
}
}
}
if (chk)
break;
}
}
}
static void input() throws Exception {
st = new StringTokenizer(br.readLine());
N = Integer.parseInt(st.nextToken());
dict = new String[N];
list = new char[4][4];
for (int i = 0; i < N; i++) {
dict[i] = br.readLine();
}
br.readLine();
st = new StringTokenizer(br.readLine());
M = Integer.parseInt(st.nextToken());
for (int i = 0; i < M; i++) {
for (int j = 0; j < 4; j++) {
st = new StringTokenizer(br.readLine());
list[j] = st.nextToken().toCharArray();
}
func();
sb.append(maxscore + " " + maxlength + " " + ans + "\n");
maxscore = 0;
maxlength = "";
ans = 0;
if (i == M - 1)
break;
br.readLine();
}
}
public static void main(String[] args) throws Exception {
input();
System.out.println(sb.toString());
}
}
|
cs |
'algorithm > dfs' 카테고리의 다른 글
| boj 16926 배열 돌리기 1 (0) | 2021.02.10 |
|---|---|
| boj 1068 트리 (0) | 2021.02.09 |
| boj 15666 N과 M (12) (0) | 2021.01.31 |
| boj 15665 N과 M (11) (0) | 2021.01.30 |
| boj 15664 N과 M (10) (0) | 2021.01.30 |