백준 9202번 : Boggle - 트라이 Java

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

9202번: Boggle

1. 문제 설명

300,000개의 word를 트라이로 만든 후

주어지는 4x4 그리드에 대해서 DFS를 수행하며 해당 문자열이 트라이 내에 존재하는지 확인하여

문제를 해결할 수 있다.

 

 

2. 문제풀이코드 Java

//package org.example;

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

public class Main {
    //trie 만들기
    final int MX = 26;
    private Trie root = new Trie();

    //dfs
    private final int[] dx = {1, 1, 1, -1, -1, -1, 0, 0};
    private final int[] dy = {0, -1, 1, 0, -1, 1, -1, 1};
    private boolean[][] visit = new boolean[4][4];
    private String[] grid = new String[4];

    //결과
    private TreeSet<String> set = new TreeSet<>();
    private HashMap<Integer, Integer> pointMap = new HashMap<Integer, Integer>() {{
        put(1, 0);
        put(2, 0);
        put(3, 1);
        put(4, 1);
        put(5, 2);
        put(6, 3);
        put(7, 5);
        put(8, 11);
    }};


    class Trie {
        Trie[] child;
        boolean isFinish;

        public Trie() {
            child = new Trie[MX];
            Arrays.fill(child, null);
            isFinish = false;
        }

        public void insert(String str) {
            Trie tmp = this;
            for (int i = 0; i < str.length(); i++) {
                int idx = str.charAt(i) - 'A';
                if (tmp.child[idx] == null) {
                    tmp.child[idx] = new Trie();
                }
                tmp = tmp.child[idx];
            }
            tmp.isFinish = true;
        }

        public void search(int x, int y, String key) {
            if (key.length() > 8) return;
            visit[x][y] = true;

            char cur = grid[x].charAt(y);
            key += cur;

            Trie tmp = this.child[cur - 'A'];
            if (tmp == null) {
                visit[x][y] = false;
                return;
            }
            if (tmp.isFinish) {
                set.add(key);
            }

            for (int dir = 0; dir < 8; dir++) {
                int nx = x + dx[dir];
                int ny = y + dy[dir];
                if (nx < 0 || nx >= 4 || ny < 0 || ny >= 4) continue;
                if (visit[nx][ny]) continue;
                tmp.search(nx, ny, key);
            }
            visit[x][y] = false;
        }
    }


    public void solution() throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();
        int n = Integer.parseInt(br.readLine());

        //Trie 생성
        for (int i = 0; i < n; i++) {
            String str = br.readLine();
            root.insert(str);
        }
        br.readLine();
        int b = Integer.parseInt(br.readLine());

        for (int i = 0; i < b; i++) {
            set.clear();

            for (int j = 0; j < 4; j++) {
                grid[j] = br.readLine();
            }
            if (i != b - 1) br.readLine();

            //dfs search
            for (int x = 0; x < 4; x++) {
                for (int y = 0; y < 4; y++) {
                    root.search(x, y, "");
                }
            }

            //결과 출력
            int point = 0, words = 0, maxLen = -1;
            String longestStr = "";
            for (String s : set) {
                int cur = s.length();
                if (cur > maxLen) {
                    maxLen = cur;
                    longestStr = s;
                }
                point += pointMap.get(cur);
                words += 1;
            }
            sb.append(point).append(" ").append(longestStr).append(" ").append(words).append("\n");
        }
        System.out.println(sb);
    }

    public static void main(String[] args) throws Exception {
        new Main().solution();
    }
}