[Java]백준 9202 Boggle

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

public class Main {

    // 루트 노드 별도로 저장
    static Node root;

    // Trie 노드
    static class Node {
        char c;
        Node[] children;
        boolean isFinished;

        // 생성자
        Node(char c) {
            this.c = c;
            this.children = new Node[26];
            this.isFinished = false;
        }

        // 자식이 없다면 추가 후 자식 참조값 리턴
        Node add(char c) {
            Node temp = this.children[c - 'A'];
            if (temp != null) return temp;

            Node child = new Node(c);
            this.children[c - 'A'] = child;
            return child;
        }

        // 자식이 있는지 여부 확인
        boolean hasChild() {
            if (children == null) return false;
            for (Node child : children)
                if (child != null) return true;
            return false;
        }
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int N = Integer.parseInt(br.readLine());

        // 루트노드 생성
        root = new Node('r');

        for (int i = 0; i < N; i++) {
            char[] word = br.readLine().toCharArray();
            Node temp = root;

            // 단어 순서대로 따라가면서 자식 노드 추가
            for (char c : word) {
                temp = temp.add(c);
            }

            // 마지막 알파벳에 플래그 표시
            temp.isFinished = true;
        }

        br.readLine();

        int b = Integer.parseInt(br.readLine());

        // DFS 결과 저장할 HashSet
        Set<String> result = new HashSet<>();
        for (int i = 0; i < b; i++) {

            // 새로운 boggle 입력
            char[][] boggle = new char[4][4];
            for (int j = 0; j < 4; j++) {
                boggle[j] = br.readLine().toCharArray();
            }

            for (int r = 0; r < 4; r++) {
                for (int c = 0; c < 4; c++) {

                    // 첫번째 자식부터 탐색
                    Node temp = root.children[boggle[r][c] - 'A'];
                    if (temp == null) continue;

                    // 첫번째 자식 현재위치에 넣고 탐색 시작
                    StringBuilder sb = new StringBuilder();
                    sb.append(boggle[r][c]);
                    dfs(boggle, result, r, c, temp, sb, new boolean[4][4]);
                }
            }

            printAnswer(result);
            result.clear();
            if (i != b - 1) br.readLine();
        }
    }

    // DFS + Backtracking
    static int[] dr = {0, 0, 1, -1, 1, 1, -1, -1};
    static int[] dc = {1, -1, 0, 0, 1, -1, -1, 1};
    static void dfs(char[][] boggle, Set<String> result, int r, int c, Node temp, StringBuilder sb, boolean[][] isVisited) {
        isVisited[r][c] = true;

        // 단어가 있는 위치에 도달하면 해당 단어 추가
        if (temp.isFinished) {
            result.add(sb.toString());

            // 현재 위치 아래에 자식이 없다면 가지치기
            if (!temp.hasChild()) return;
        }

        // 8방향 탐색
        for (int i = 0; i < 8; i++) {
            int nr = r + dr[i];
            int nc = c + dc[i];

            if (nr < 0 || nr >= 4 || nc < 0 || nc >= 4 || isVisited[nr][nc]) continue;
            if (temp.children[boggle[nr][nc] - 'A'] == null) continue;

            // 다음 단어 추가
            sb.append(boggle[nr][nc]);
            dfs(boggle, result, nr, nc, temp.children[boggle[nr][nc] - 'A'], sb, isVisited);

            // DFS 복귀 후 값 초기화
            sb.deleteCharAt(sb.length() - 1);
            isVisited[nr][nc] = false;
        }
    }

    // 정답 출력
    static int[] scoreMap = {0, 0, 0, 1, 1, 2, 3, 5, 11};
    static void printAnswer(Set<String> result) {
        int maxLength = 0;
        int score = 0;
        List<String> maxs = new ArrayList<>();
        for (String r : result) {

            // 총점에 현재단어 길이 점수 추가
            score += scoreMap[r.length()];
            if (r.length() > maxLength) {
                maxLength = r.length();
                maxs.clear();
                maxs.add(r);

                // 가장 긴 단어 여러개일 경우 저장
            } else if (r.length() == maxLength) {
                maxs.add(r);
            }
        }

        // 가장 긴 단어 여러개일 경우 오름차순 정렬
        maxs.sort(Comparator.naturalOrder());

        // 총점 + 가장 긴 단어 + 결과 크기 출력
        System.out.println(score + " " + maxs.get(0) + " " + result.size());
    }

}