[백준 - 9202] Boggle - Java

https://www.acmicpc.net/problem/9202

9202번: Boggle

 

Trie를 사용해서 푸는 문제이다.

 

트라이는 문자열을 빠르게 검색할 수 있는 자료구조이다. 

// Trie 노드 설계

class Node {
	Object data;
    Node[] child; // a~z까지 담을 수 있도록 26크기의 배열 
}

 

add, ade, car, dad가 insert된 트라이는 아래와 같다.

 

트라이를 이용하여 검색할 때

- 루트부터 시작하여 검색할 단어의 첫글자부터 트라이를 탐색

- 현재 노드의 자식 노드 중 현재 철자에 해당하는 자식이 있다면 해당 자식 노드로 이동

- 해당하는 자식이 없다면 존재하지 않는 단어로 처리

- 탐색이 완료되었다면 탐색된 마지막 노드의 정보를 이용

 

 

하지만 만약 위의 그림에서 'ad'라는 단어가 있다고 생각할 수 있을까?

'ad'같은 내부노드에 단어가 있을 수도 있는 경우를 생각하기 위해서 Node 클래스에 isEnd라는 변수를 만들어서 표시한다. 

 

---

이제 본격적으로 문제풀이에 들어서서

 

- 각각의 Boggle에 대해 Boggle에서 같은 단어를 여러 번 찾은 경우에는 한 번만 찾은 것으로 센다.

 

같은 단어를 여러 번 찾은 경우에 한 번만 찾은 것으로 센다고 했기 때문에, Trie의 노드에 isHit이라는 boolean 변수를 사용해서 이미 찾은 단어인지 체크하고, 매 보글마다 초기화한다.

class Node {
    String data;
    Node[] child;
    boolean isEnd;
    boolean isHit;

    public Node(String data, boolean isEnd, boolean isHit) {
        this.data = data;
        this.isEnd = isEnd;
        this.isHit = isHit;
        child = new Node[26];
    }

    @Override
    public String toString() {
        return "Node{" +
                "data='" + data + '\'' +
                ", child=" + Arrays.toString(child) +
                '}';
    }

    void clearHit(){
        isHit = false;
        for (Node node : child) {
            if(node != null) node.clearHit();
        }
    }
}

public class Main {
    static final int[] score = {0, 0, 0, 1, 1, 2, 3, 5, 11};
    static final int[] mx = { 0, 1, 1, 1, 0, -1, -1, -1};
    static final int[] my = { -1, -1, 0, 1, 1, 1, 0, -1};
    static char[][] map;
    static boolean[][] visit;
    static Node trie;

    static String longestWord;
    static int maxScore;
    static int wordCount;

    public static void main(String[] args) throws Exception{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());


        // trie 입력
        trie = new Node(null, false, false);
        for(int i=0; i<N; i++){
            String input = br.readLine().trim();
            Node v = trie;
            StringBuilder data = new StringBuilder();
            for(int j=0; j<input.length(); j++){
                int c = input.charAt(j)-'A';
                Node next = v.child[c];
                data.append((char)('A'+c));
                if(next==null) {
                    next = new Node(data.toString(), false, false);
                    v.child[c] = next;
                }
                v = v.child[c];
            }
            v.isEnd = true;
        }
        br.readLine();

        int b = Integer.parseInt(br.readLine());
        for(int i=0; i<b; i++){
            visit = new boolean[4][4];
            map = new char[4][4];
            // Boggle 보드 입력
            for(int j=0; j<4; j++){
                String s = br.readLine();
                for(int k=0; k<4; k++){
                    map[j][k] = s.charAt(k);
                }
            }

            if(i<b-1) br.readLine();


            longestWord = "";
            maxScore = 0;
            wordCount = 0;
            for(int j=0; j<4; j++){
                for(int k=0; k<4; k++){
                    char c = map[j][k];
                    if(trie.child[c-'A']!=null){
                        StringBuilder sb = new StringBuilder();
                        sb.append(c);
                        DFS(0, j, k, sb.toString(), trie.child[c-'A']);
                        //System.out.println(longestWord+" "+maxScore+" "+wordCount);
                    }

                }
            }
            StringBuilder sb = new StringBuilder();
            sb.append(maxScore+" "+longestWord+" "+wordCount);
            System.out.println(sb.toString().replaceAll("\\s+", " "));

            trie.clearHit();
        }



    }

    static void DFS(int length, int row, int col, String word, Node wordNode){
        // 1. 체크인
        visit[row][col] = true;
        // 2. 목적지인가? ( isEnd = true, isHit = false)
        if(wordNode.isEnd && !wordNode.isHit){
            if(longestWord.length() < word.length()) longestWord = word;
            else if(longestWord.length() == word.length()) longestWord = longestWord.compareTo(word)<0? longestWord:word;
            maxScore += score[word.length()];
            wordCount++;
            wordNode.isHit = true;
            visit[row][col] = false;
            return;
        }
        // 3. 연결된 곳 : 8방향
        for(int i=0; i<8; i++){

            int nextRow = row + my[i];
            int nextCol = col + mx[i];

            // 4. 갈 수 있는가? ( 맵 내부, trie, 방문하지 않은 지점)
            if(nextRow >= 0 && nextRow < 4 && nextCol >= 0 && nextCol < 4
            && wordNode.child[map[nextRow][nextCol]-'A'] != null
            && visit[nextRow][nextCol]==false){
                // 5. 간다
                char c = map[nextRow][nextCol];

                // 다음 노드
                Node next = wordNode.child[c-'A'];
                StringBuilder sb = new StringBuilder(word);
                sb.append(c);

                DFS(length+1, nextRow, nextCol, sb.toString(), next);
            }
        }
        // 6. 체크 아웃
        visit[row][col] = false;

    }
}