<Trie> BOJ 9202 Boggle

문제

Boggle이라는 보드 게임에서의 최대 점수를 얻는 방법을 찾는 문제로 유의 사항으로는 10초라는 시간 제한이 있다는 점입니다. 10초가 아니라면 해결 방법이 있는지는 모르겠습니다.

• 단어의 수 w < 300000
• 보드의 개수 b < 30

접근

• 1. 주어진 단어를 Trie 자료 구조를 정의하여 모두 저장한다.

• 2. 각 보드에 대해 각 16개의 주사위를 시작점으로 하는 모든 가능한 문자열을 구하고 문자열을 Trie 자료 구조와 비교하여 사전에 존재하는 단어라면 HashSet<String>에 저장해준다.
  • 2-1. 그런데 모든 경우를 돌면 경우의 수가 매우 크기 때문에 백트랙킹 과정이 필요합니다.. 이것을 구현하기 위해 Trie의 search를 두개의 boolean을 return 하도록 했습니다. 하나는 현재 탐색중인 단어가 trie에 저장된 단어의 prefix가 되는가? prefix가 된다면 trie에 포함된 단어인가? 두 개의 값을 받아 prefix가 아니라면 더 진행하더라도 사전에 포함된 단어가 될 수 없으므로 백트랙킹 해주는 과정이 코드에 포함되어 있습니다.

• 3. 문제에서 가장 긴 단어가 여러개라면 사전순으로 가장 먼저 오는 단어를 출력하라고 했으므로 set을 ArrayList로 변환한 후 Comparator를 따로 정의해서 정렬해주면 좋습니다.

코드

import java.io.*;
import java.util.*;

class Node {
    int[] children;
    boolean valid;

    Node() {
        children = new int[26];
        Arrays.fill(children, -1);
        valid = false;
    }
}

class Trie {
    ArrayList<Node> trie;
    int root;

    int init() {
        Node x = new Node();
        trie.add(x);
        return trie.size() - 1;
    }

    Trie() {
        trie = new ArrayList<>();
        root = init();
    }

    void add(String s, int idx, int cur) {
        if (idx == s.length()) {
            trie.get(cur).valid = true;
            return;
        }

        int c = s.charAt(idx) - 'A';
        if (trie.get(cur).children[c] == -1) {
            int nex = init();
            trie.get(cur).children[c] = nex;
        }

        int nex = trie.get(cur).children[c];
        add(s, idx + 1, nex);
    }

    void add(String s) {
        add(s, 0, root);
    }

    Pair search(String s, int idx, int cur) {
        if (idx == s.length()) {
            return new Pair(true, trie.get(cur).valid);
        }

        int c = s.charAt(idx) - 'A';
        if (trie.get(cur).children[c] == -1)
            return new Pair(false, false);

        int nex = trie.get(cur).children[c];
        return search(s, idx + 1, nex);
    }

    Pair search(String s) {
        return search(s, 0, root);
    }
}

class Pair {
    boolean prefix;
    boolean valid;

    Pair(boolean prefix, boolean valid) {
        this.prefix = prefix;
        this.valid = valid;
    }
}

class customComparator implements Comparator<String> {
    public int compare(String a, String b) {
        if (a.length() < b.length()) {
            return -1;
        } else if (a.length() == b.length()) {
            return -a.compareTo(b);
        }
        return 1;
    }
}

class baek__9202 {
    static Trie trie;
    static int[] dx = { -1, 0, 1, 0, 1, 1, -1, -1 };
    static int[] dy = { 0, -1, 0, 1, -1, 1, 1, -1 };
    static HashSet<String> set = new HashSet<>();

    static boolean[][] check = new boolean[4][4];

    static int getPoint(String s) {
        if (s.length() == 8) {
            return 11;
        } else if (s.length() == 7) {
            return 5;
        } else if (s.length() == 6) {
            return 3;
        } else if (s.length() == 5) {
            return 2;
        } else if (s.length() == 4 || s.length() == 3) {
            return 1;
        }
        return 0;
    }

    static void go(int x, int y, String[] map, String cur) {
        Pair pair = trie.search(cur);
        if (pair.prefix) {
            if (pair.valid)
                set.add(cur);
        } else {
            return;
        }

        for (int k = 0; k < 8; k++) {
            int nx = x + dx[k];
            int ny = y + dy[k];
            if (nx < 0 || nx >= 4 || ny < 0 || ny >= 4)
                continue;
            if (check[nx][ny])
                continue;
            check[nx][ny] = true;
            go(nx, ny, map, cur + map[nx].charAt(ny));
            check[nx][ny] = false;
        }
    }

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

        int n = Integer.parseInt(br.readLine());
        trie = new Trie();
        for (int i = 0; i < n; i++) {
            trie.add(br.readLine());
        }

        br.readLine();
        int m = Integer.parseInt(br.readLine());
        StringBuilder sb = new StringBuilder();
        while (m-- > 0) {
            String[] map = new String[4];
            for (int i = 0; i < 4; i++) {
                map[i] = br.readLine();
            }
            for (int i = 0; i < 4; i++) {
                for (int j = 0; j < 4; j++) {
                    check[i][j] = true;
                    go(i, j, map, Character.toString(map[i].charAt(j)));
                    check[i][j] = false;
                }
            }
            ArrayList<String> list = new ArrayList(set);
            set.clear();
            long points = 0;
            for (int i = 0; i < list.size(); i++) {
                String s = list.get(i);
                points += getPoint(s);
            }
            Collections.sort(list, new customComparator());
            sb.append(points + " " + list.get(list.size() - 1) + " " + list.size() + "\n");
            if (m != 0) {
                br.readLine();
            }
        }

        System.out.print(sb);

    }
}