[백준] 9202: Boggle [Java]

 

알고리즘 분류: 트라이, 백트래킹

문제 링크: https://www.acmicpc.net/problem/9202

 

 

 

 

---

【 문제 】

 

•  4*4 격자판에 알파벳들이 주어지면, 각 문자에서 8방 탐색을 해 문자열을 구성하고, 그 문자열이 찾고자 하는 문자열 리스트에 들어있는지 여부에 따라 총 점수, 가장 긴 문자열, 찾은 문자 개수를 갱신하는 문제이다.
• 주의해야할 점은 같은 위치의 문자를 두 번 이상 사용할 수 없다(다시 방문할 수 없다)는 것, 이미 찾은 문자열에 대해서는 점수를 올리거나 문자 개수를 올리지 않는다는 점이다.

 

 

---

【 풀이 】

• 찾아야 할 단어 목록을 트라이로 구성.
• 이때 트라이 노드에 단어의 끝을 나타내는 문자인 `*` 을 넣어줬다
• 격자판에서 인접한 문자를 고르면서 문자열을 조합해내야 하기 때문에 DFS로 문자열 구성
• 다음 문자가 다음 트라이 노드에 있는지 없는지(없으면 그 경우는 건너뛰면 됨), 다음 좌표가 격자판을 벗어나는지, 그리고 그 곳이 방문한 곳인지를 체크하기
• 따라서 파라미터로 다음 트라이 노드를 넘겨주면서 DFS
• 현재 트라이 노드에 `*` 이 있으면 정답을 갱신한다. 구성한 문자열을 찾은 문자열 set에 넣고 종료는 하지 않는다
• 재귀를 종료하지 않는 이유는 현재 발견한 문자열보다 더 긴 문자열이 목록에 포함되어 있는 경우가 있기 때문이다

 

 

---

 

 

【 코드 】

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.HashMap;
import java.util.HashSet;
import java.util.Map;
import java.util.Set;

public class BOJ_9202 {
    static class TrieNode {
        Map<Character, TrieNode> children;

        TrieNode(){
            children=new HashMap<>();
        }
    }

    static class Trie {
        TrieNode root;

        Trie(){
            root=new TrieNode();
        }
    }

    static final int[] dy={-1,1,0,0,-1,-1,1,1};
    static final int[] dx={0,0,-1,1,-1,1,-1,1};
    static StringBuilder sb=new StringBuilder();
    static BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
    static Trie t;
    static char[][] arr;
    static boolean[][] visited;
    static Set<String> found;
    static int score;
    static String maxString="";
    static int count;

    public static void main(String[] args)throws IOException {
        t=new Trie();
        int n=Integer.parseInt(br.readLine());
        for(int i=0;i<n;i++){
            String s=br.readLine();
            TrieNode temp=t.root;
            for(int j=0;j<s.length();j++){
                temp=temp.children.computeIfAbsent(s.charAt(j),a->new TrieNode());
            }
            temp.children.put('*',new TrieNode());
        }

        br.readLine();
        int b=Integer.parseInt(br.readLine());
        for(int i=0;i<b;i++){
            score=0;
            maxString="";
            count=0;
            arr=new char[4][4];
            found=new HashSet<>();
            for(int j=0;j<4;j++){
                arr[j]=br.readLine().toCharArray();
            }
            for(int j=0;j<4;j++){
                for(int k=0;k<4;k++){
                    if(!t.root.children.containsKey(arr[j][k]))continue;

                    visited=new boolean[4][4];
                    visited[j][k]=true;
                    play(j,k,arr[j][k]+"",t.root.children.get(arr[j][k]));
                }
            }
            br.readLine();
            sb.append(score).append(" ").append(maxString).append(" ").append(count).append("\n");
        }
        System.out.print(sb);
    }

    private static void play(int y,int x,String s,TrieNode temp){
        if(temp.children.containsKey('*')&&found.add(s)){
            score+=cal(s);
            maxString=compare(maxString, s);
            count++;
        }
        for(int i=0;i<8;i++){
            int ny=y+dy[i];
            int nx=x+dx[i];

            if(ny<0||nx<0||ny>=4||nx>=4)continue;
            if(visited[ny][nx])continue;
            if(!temp.children.containsKey(arr[ny][nx]))continue;

            visited[ny][nx]=true;
            play(ny,nx,s+arr[ny][nx],temp.children.get(arr[ny][nx]));
            visited[ny][nx]=false;
        }
    }

    private static int cal(String s) {
        int size=s.length();
        if(size<3)return 0;
        else if(size<5)return 1;
        else if(size<6)return 2;
        else if(size<7)return 3;
        else if(size<8)return 5;
        return 11;
    }

    private static String compare(String s1, String s2) {
        if(s1.length()<s2.length())return s2;
        else if(s1.length()>s2.length())return s1;
        else {
            int res=s1.compareTo(s2);
            if(res<0)return s1;
            else return s2;
        }
    }
}