[자바] 백준 9202 - Boggle (java)

목차

문제 : boj9202

 

 

필요 알고리즘

• 브루트포스, 백트래킹, 그래프 탐색(dfs 혹은 bfs 등), 트리, 트라이(Trie)
  
  • 원래 플래급 가면 여러가지 섞어야 하는 경우가 많긴하다. 내 경우엔 메인 알고리즘은 트라이였고, 나머진 트라이로 로직 구현을 위한 부가적인 부분이었다.

※ 제 코드에서 왜 main 함수에 로직을 직접 작성하지 않았는지, 왜 Scanner를 쓰지 않고 BufferedReader를 사용했는지 등에 대해서는 '자바로 백준 풀 때의 팁 및 주의점' 글을 참고해주세요. 백준을 자바로 풀어보려고 시작하시는 분이나, 백준에서 자바로 풀 때의 팁을 원하시는 분들도 보시는걸 추천드립니다.

 

 

풀이

  일단 내 경우엔 트라이로 풀었는데, 의견쪽을 보니 시간이 널널해서 그냥 해싱 처리해도 된다고 한다. 그쪽이 훨씬 구현은 간단할 것 같다. 아무튼 이하 풀이는 트라이 기준이다.

 

  우선 4x4의 판에서 만들 수 있는 모든 문자를 알아내려면 dfs, bfs 같은 그래프 탐색으로 모든 경우를 보면 된다.(브루트포스)

 

  근데 그럼 시간복잡도가 높아지니, 내 경우엔 이걸 백트래킹으로 쳐내기 위해서 (존재하지 않는 문자라면 dfs 진행 중간에 튕겨내도록) 트라이를 사용하기로 했다.

 

  처음에 w개의 단어를 모두 트라이로 등록해둔다. 이 때, 단어가 완성되는 지점은 별도로 체크해두고 해당 단어를 넣어둔다. 예를들어 "heaven, hello, hell, goodbye" 이렇게 단어가 주어졌다면 아래처럼 트라이를 만든다. 붉은 지점이 단어가 완성되는 지점이다. (문제는 대문자만 주어지니 대문자라 생각하고 보자! 어차피 소문자든 대문자든 다른점은 없다.)

 

  이제 b개의 4x4 보드를 dfs 등으로 탐색하면서 한칸씩 진행해보는거다. 예를들어 보드에서 현재 시작한 문자열이 'z'라면 트라이의 루트에서 'z'로 진행하는 쪽이 없으니 무시한다(백트래킹). 'h'라면 h쪽으로 이동한다. 그다음 또 'a'가 나왔다면 진행할곳이 없으니 무시하고(백트래킹), 'e'라면 진행한다. 이런식으로 진행하다가 단어가 완성되는 빨간색 지점을 만나면 해당 단어의 점수를 얻는다.

 

  예를들어 h->e->l->l->o 로 진행했다면 길이가 5이니 2점이다. 이걸 최대 점수에 합산하고, 찾은 단어의 개수를 1 증가하고, 가장 긴 단어는 별도로 체크해주면 된다!

 

  말로 설명하면 참 쉬운데, 언제나 그렇듯 이걸 구현하기는 녹록치 않긴하다 ㅋㅋㅋ

 

 

코드 : github

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.HashSet;
import java.util.Set;

public class Main {
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

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

    private void solution() throws Exception {
        TrieRoot trie = setupTrie();
        StringBuilder answer = new StringBuilder();

        int b = Integer.parseInt(br.readLine());
        while (b-->0) {
            char[][] boggle = new char[4][4];
            for (int i = 0; i < 4; i++) {
                String row = br.readLine();
                for (int j = 0; j < 4; j++) {
                    boggle[i][j] = row.charAt(j);
                }
            }

            if (b!=0) br.readLine();    // drop blank line

            FindBoggleResult findBoggleResult = new FindBoggleResult(trie, boggle, answer);
            findBoggleResult.findAndPrintAnswer();
        }

        System.out.print(answer);
    }

    private TrieRoot setupTrie() throws Exception {
        TrieRoot trie = new TrieRoot();

        int w = Integer.parseInt(br.readLine());
        while (w-->0) {
            trie.add(br.readLine());
        }
        br.readLine();  // drop blank line

        return trie;
    }
}

class FindBoggleResult {
    TrieRoot trie;
    char[][] boggle;
    int scoreSum;
    String maxLenWord;
    int cnt;
    StringBuilder answer;
    boolean[][] v;
    Set<String> alreadyFound;

    public FindBoggleResult(TrieRoot trie, char[][] boggle, StringBuilder answer) {
        this.trie = trie;
        this.boggle = boggle;
        this.answer = answer;
        scoreSum = 0;
        maxLenWord = null;
        cnt = 0;
        v = new boolean[4][4];
        alreadyFound = new HashSet<>();
    }

    public void findAndPrintAnswer() {
        for (int i = 0; i < 4; i++) {
            for (int j = 0; j < 4; j++) {
                v[i][j] = true;
                find(1, i, j, trie.root.peek(boggle[i][j]));
                v[i][j] = false;
            }
        }

        answer.append(scoreSum).append(' ')
                .append(maxLenWord).append(' ')
                .append(cnt).append('\n');
    }

    private void register(String word) {
        if (alreadyFound.contains(word)) return;
        alreadyFound.add(word);
        cnt++;

        int score = getScore(word);
        scoreSum += score;

        if (maxLenWord == null) {
            maxLenWord = word;
            return;
        }

        if (maxLenWord.length() < word.length() || (word.length() == maxLenWord.length() && word.compareTo(maxLenWord) < 0)) {
            maxLenWord = word;
        }
    }

    private int getScore(String word) {
        int len = word.length();
        if (len <= 2) return 0;
        if (len <= 4) return 1;
        if (len == 5) return 2;
        if (len == 6) return 3;
        if (len == 7) return 5;
        if (len == 8) return 11;
        return 0;
    }

    private void find(int cnt, int r, int c, Node node) {
        if (node == null || cnt == 9) return;
        if (node.isWordExist()) register(node.getWord());

        for (int i = -1; i <= 1; i++) {
            for (int j = -1; j <= 1; j++) {
                int nr = r+i;
                int nc = c+j;

                if (nr<0 || nr>=4 || nc<0 || nc>=4 || v[nr][nc]) continue;
                v[nr][nc] = true;
                find(cnt+1, nr, nc, node.peek(boggle[nr][nc]));
                v[nr][nc] = false;
            }
        }
    }
}

class TrieRoot {

    Node root;

    public TrieRoot() {
        root = Node.root();
    }

    public void add(String s) {
        Node iter = root;

        for (int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);

            iter = iter.retrieveChild(c);
        }

        iter.endOfWord(s);
    }
}

class Node {
    private String word;
    private Node[] child;

    private Node() {
        word = null;
        child = new Node['Z'-'A'+1];
    }

    public static Node root() {
        return new Node();
    }

    public void endOfWord(String s) {
        word = s;
    }

    public Node retrieveChild(char c) {
        int idx = c - 'A';

        if (child[idx] == null) {
            child[idx] = new Node();
        }

        return peek(c);
    }

    public Node peek(char c) {
        int idx = c - 'A';

        return child[idx];
    }

    public boolean isWordExist() {
        return word != null;
    }

    public String getWord() {
        return word;
    }
}