[BOJ] 9202. Boggle

Trie와 백트래킹을 이용한 시뮬레이션 문제이다.

이 문제를 맨처음 보았을 때 일종의 사전 개념인 처음 5개의 입력을 보고 Trie 알고리즘을 사용할 생각을 하였다. 그리고 map이 4x4로써 크지 않고, 주어진 시간도 10초로 충분하여서 백트래킹을 통해 만들어질수 있는 모든 단어에 대해 Trie search를 해주는 방식으로 접근하였다.

여러가지 알고리즘이 혼합되어 있는 형태이기때문에 작은 실수만 해도 어려워 질수 있었던 문제였다. Trie와 다른 알고리즘을 같이 사용해볼 수 있던 좋은 문제였던 것 같다.

package study5;
 
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Collections;
import java.util.HashSet;
import java.util.List;
import java.util.Set;
import java.util.StringTokenizer;
 
public class Main_bj_9202_Boggle {
    
    static class Pos{
        int i,j;
        Pos(int i,int j){
            this.i=i;this.j=j;
        }
    }
    
    static class Node{
        boolean isEnd;
        Node[] child;
        Node(){
            isEnd=false;child=new Node[26];
        }
    }
    
    static class Boggle implements Comparable<Boggle>{
        String word; int score;
        Boggle(String w, int s) {
            word=w;score=s;
        }
        @Override
        public int compareTo(Boggle o) {
            if(score==o.score) {
                return word.compareTo(o.word);
            }
            return -Integer.compare(score, o.score);
        }
    }
    
    static List<Boggle> list;
    static Set<String> set;
    
    
    static int[] di= {-1,-1,0,1,1,1,0,-1};
    static int[] dj= {0,1,1,1,0,-1,-1,-1};
    
    static Node root;
    static char[][] map;
    static boolean[][] visit;
    
    
    
    public static void main(String[] args) throws Exception {
        BufferedReader br= new BufferedReader(new InputStreamReader(System.in));
        int N=Integer.parseInt(br.readLine());
        root=new Node();
        for(int i=0;i<N;i++) {
            String str= br.readLine();
            insert(str);
        }
        
        br.readLine();
        
        int T=Integer.parseInt(br.readLine());
        
        for(int tc=0;tc<T;tc++) {
            set=new HashSet<>();
            list=new ArrayList<>();
            map=new char[4][4];
            visit=new boolean[4][4];
            
            for(int i=0;i<4;i++) {
                String line =br.readLine();
                for(int j=0;j<4;j++) {
                    map[i][j]=line.charAt(j);
                }
            }
            
            
            for(int i=0;i<4;i++) {
                for(int j=0;j<4;j++) {
                    visit[i][j]=true;
                    dfs(i,j,1,map[i][j]+"");
                    visit[i][j]=false;
                }
            }
            
            int sum=0;
            for(String str :set) {
                int num=strToScore(str);
                sum+=num;
                list.add(new Boggle(str, num));
            }
            
            Collections.sort(list);
            
            System.out.println(sum+" "+list.get(0).word + " "+ set.size() );
            
            
            br.readLine();
        }
    }
 
    static void dfs(int i,int j,int count,String str) {
        if(count ==9) {
            return;
        }
        
        if(search(str)==true) {
            set.add(str);
        }
        
        for(int dir=0;dir<8;dir++) {
            int nextI=i+di[dir];
            int nextJ=j+dj[dir];
            
            if(nextI<0 || nextI>=4 || nextJ<0 || nextJ>=4)
                continue;
            
            if(visit[nextI][nextJ]==false) {
                visit[nextI][nextJ]=true;
                dfs(nextI,nextJ,count+1,str+map[nextI][nextJ]);
                visit[nextI][nextJ]=false;
            }
            
        }
    }
    
    static int strToScore(String str) {
        int len=str.length();
        if(len==1  || len ==2) {
            return 0;
        }else if(len==3  || len ==4) {
            return 1;
        }else if(len==5) {
            return 2;
        }else if(len==6) {
            return 3;
        }else if(len==7) {
            return 5;
        }else if(len==8) {
            return 11;
        }
        return 0;
    }
 
    static boolean search(String str) {
        Node cur=root;
        
        for(int i=0;i<str.length();i++) {
            int alp=str.charAt(i)-'A';
            
            if(cur.child[alp]==null)
                return false;
            
            cur=cur.child[alp];
        }
        
        if(cur.isEnd==true)
            return true;
        return false;
        
    }
    
    
    static void insert(String str) {
        Node cur= root;
        
        for(int i=0;i<str.length();i++) {
            int alp=str.charAt(i)-'A';
            
            if(cur.child[alp]==null) {
                cur.child[alp]=new Node();
            }
            
            cur=cur.child[alp];
        }
        cur.isEnd=true;
    }
}