자료구조 공부/Trie
백준 9202 (Boggle)
kdhoooon
2021. 3. 16. 12:22
문제
상근이는 보드 게임 "Boggle"을 엄청나게 좋아한다. Boggle은 글자가 쓰여 있는 주사위로 이루어진 4×4 크기의 그리드에서 최대한 많은 단어를 찾는 게임이다.
상근이는 한 번도 부인을 Boggle로 이겨본 적이 없다. 이렇게 질 때마다 상근이는 쓰레기 버리기, 설거지와 같은 일을 해야 한다. 이제 상근이는 프로그램을 작성해서 부인을 이겨보려고 한다.
Boggle에서 단어는 인접한 글자(가로, 세로, 대각선)를 이용해서 만들 수 있다. 하지만, 한 주사위는 단어에 한 번만 사용할 수 있다. 단어는 게임 사전에 등재되어 있는 단어만 올바른 단어이다.
1글자, 2글자로 이루어진 단어는 0점, 3글자, 4글자는 1점, 5글자는 2점, 6글자는 3점, 7글자는 5점, 8글자는 11점이다. 점수는 자신이 찾은 단어에 해당하는 점수의 총 합이다.
단어 사전에 등재되어 있는 단어의 목록과 Boggle 게임 보드가 주어졌을 때, 얻을 수 있는 최대 점수, 가장 긴 단어, 찾은 단어의 수를 구하는 프로그램을 작성하시오.
풀이
이 문제는 우선 Trie 자료구조 알고리즘과 DFS 알고리즘을 이용하는 문제다.
우선 먼저 주어지는 사전 단어들을 Trie 자료구조 형태로 저장을 한다.
Trie 자료구조는 단어들을 tree 형태로 저장을 해놓는 것을 말한다.
위 와 같은 방식으로 트리형태로 만들어 놓고 시작한다.
위 그림에서는 제외 했으나 각각 마지막 문자 끝에는 마지막 단어라는 것을 표현해 주어야 한다.
필자는 Boolean 값으로 표현했다.
Trie는 클레스로 하나의 형태를 만들어 주었다.
<Trie Class>
public static class Node{
char data;
boolean isEnd;
Node[] child;
Node(char c){
data = c;
child = new Node[27];
}
Node setChild(char c) {
if( c == '\0') {
isEnd = true;
return null;
}
if( child[ c - 'A'] == null)
child[ c - 'A'] = new Node(c);
return child[ c - 'A'];
}
}
public static class Trie{
Node n;
Trie(){
n = new Node('\0');
}
void add(String s) {
Node n = this.n;
for(int i = 0 ; i < s.length(); i++) {
n = n.setChild(s.charAt(i));
}
n.setChild('\0');
}
boolean isContain(int length) {
Node n = this.n;
for(int i = 0 ; i < length; i++) {
if(n.child[string[i] - 'A'] == null) {
return false;
}
n = n.child[string[i] - 'A'];
}
return n.isEnd;
}
}여기서 Node 클레스는 Trie 형태를 구성하는 하나의 노드를 클레스로 미리 만들어 준 뒤 Trie 형태를 만들었다.
Node 에서 HashMap 을 사용하는 경우도 있지만 필자의 경우에는 알파벳 27개의 배열을 모두 만든 뒤 풀었다.
4 x 4 보드에서 단어를 찾는 방식은 DFS(깊이 우선 탐색) 방식을 통해 풀었다.
상하좌우 대각선으로 모두 움직일 수 있기 때문에 아래와 같이 미리 움직임을 설정 해놓았다.
static int[] dx = {-1, 1, 0, 0, -1, -1, 1, 1};
static int[] dy = {0, 0, -1, 1, -1, 1, -1, 1};
<DFS 코드>
static void dfs(int x, int y, int depth) {
if(depth == size) {
if(trie.isContain(depth) && !hs.contains(String.copyValueOf(string)))
hs.add(String.copyValueOf(string));
return;
}
for(int i = 0 ; i < 8 ; i++) {
int nx = x + dx[i];
int ny = y + dy[i];
if(nx >= 0 && ny >= 0 && nx < 4 && ny < 4 && !visit[nx][ny]) {
string[depth] = cube[nx][ny];
visit[nx][ny] = true;
dfs(nx, ny, depth + 1);
visit[nx][ny] = false;
}
}
}정해진 횟수만큼 반복문을 통해 돌면서 시작점 부터 상하좌우 대각선 방향의 단어들을 조합했을 때 사전 속 단어가 완성이 되는지 여부를 판단을한다.
<전체코드>
import java.io.*;
import java.math.*;
import java.security.*;
import java.text.*;
import java.util.*;
import java.util.concurrent.*;
import java.util.function.*;
import java.util.regex.*;
import java.util.stream.*;
import javax.management.Query;
import static java.util.stream.Collectors.joining;
import static java.util.stream.Collectors.toList;
public class Main {
static StringBuilder sb = new StringBuilder();
public static class Node{
char data;
boolean isEnd;
Node[] child;
Node(char c){
data = c;
child = new Node[27];
}
Node setChild(char c) {
if( c == '\0') {
isEnd = true;
return null;
}
if( child[ c - 'A'] == null)
child[ c - 'A'] = new Node(c);
return child[ c - 'A'];
}
}
public static class Trie{
Node n;
Trie(){
n = new Node('\0');
}
void add(String s) {
Node n = this.n;
for(int i = 0 ; i < s.length(); i++) {
n = n.setChild(s.charAt(i));
}
n.setChild('\0');
}
boolean isContain(int length) {
Node n = this.n;
for(int i = 0 ; i < length; i++) {
if(n.child[string[i] - 'A'] == null) {
return false;
}
n = n.child[string[i] - 'A'];
}
return n.isEnd;
}
}
static int N, size;
static Trie trie = new Trie();
static char[][] cube = new char[4][4];
static boolean[][] visit = new boolean[4][4];
static char[] string;
static int[] dx = {-1, 1, 0, 0, -1, -1, 1, 1};
static int[] dy = {0, 0, -1, 1, -1, 1, -1, 1};
static HashSet<String> hs = new HashSet<>();
public static void main(String[] args) throws IOException {
BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in));
N = Integer.parseInt(bufferedReader.readLine());
for(int i = 0 ; i < N ; i++) {
trie.add(bufferedReader.readLine());
}
bufferedReader.readLine();
N = Integer.parseInt(bufferedReader.readLine());
for(int i = 0 ; i < N ; i++) {
for(int j = 0 ; j < 4 ; j++) {
char[] temp = bufferedReader.readLine().toCharArray();
for(int k = 0 ; k < 4 ; k++) {
cube[j][k] = temp[k];
}
}
hs.clear();
search();
//빈 줄 제거
if(i != N - 1)
bufferedReader.readLine();
result();
}
System.out.println(sb);
}
static void search() {
for(int i = 1; i <= 8 ; i++) {
isPossible(i);
}
}
static void isPossible(int length) {
size = length;
string = new char[size];
for(int i = 0 ; i < 4 ; i++) {
for(int j = 0 ; j < 4 ; j++) {
string[0] = cube[i][j];
visit[i][j] = true;
dfs(i, j, 1);
visit[i][j] = false;
}
}
}
static void dfs(int x, int y, int depth) {
if(depth == size) {
if(trie.isContain(depth) && !hs.contains(String.copyValueOf(string)))
hs.add(String.copyValueOf(string));
return;
}
for(int i = 0 ; i < 8 ; i++) {
int nx = x + dx[i];
int ny = y + dy[i];
if(nx >= 0 && ny >= 0 && nx < 4 && ny < 4 && !visit[nx][ny]) {
string[depth] = cube[nx][ny];
visit[nx][ny] = true;
dfs(nx, ny, depth + 1);
visit[nx][ny] = false;
}
}
}
static void result() {
ArrayList<String> list = new ArrayList<>(hs);
Collections.sort(list);
int point = 0, count = 0;
String result = "";
for(String s : list) {
if(s.length() > result.length())
result = s;
point += calculator(s);
count++;
}
sb.append(point + " " + result + " " + count + "\n");
}
static int calculator(String s) {
if( s.length() <= 2 )
return 0;
else if( s.length() == 3 )
return 1;
else if( s.length() <= 6)
return s.length() - 3;
else if( s.length() == 7)
return 5;
else if( s.length() == 8)
return 11;
else
return -1;
}
}