[백준] 9202 Boggle java

문제

상근이는 보드 게임 "Boggle"을 엄청나게 좋아한다. Boggle은 글자가 쓰여 있는 주사위로 이루어진 4×4 크기의 그리드에서 최대한 많은 단어를 찾는 게임이다. 

상근이는 한 번도 부인을 Boggle로 이겨본 적이 없다. 이렇게 질 때마다 상근이는 쓰레기 버리기, 설거지와 같은 일을 해야 한다. 이제 상근이는 프로그램을 작성해서 부인을 이겨보려고 한다.

Boggle에서 단어는 인접한 글자(가로, 세로, 대각선)를 이용해서 만들 수 있다. 하지만, 한 주사위는 단어에 한 번만 사용할 수 있다. 단어는 게임 사전에 등재되어 있는 단어만 올바른 단어이다.

1글자, 2글자로 이루어진 단어는 0점, 3글자, 4글자는 1점, 5글자는 2점, 6글자는 3점, 7글자는 5점, 8글자는 11점이다. 점수는 자신이 찾은 단어에 해당하는 점수의 총 합이다.

단어 사전에 등재되어 있는 단어의 목록과 Boggle 게임 보드가 주어졌을 때, 얻을 수 있는 최대 점수, 가장 긴 단어, 찾은 단어의 수를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 단어 사전에 들어있는 단어의 수 w가 주어진다. (1 < w < 300,000) 다음 w개 줄에는 단어가 주어진다. 단어는 최대 8글자이고, 알파벳 대문자로만 이루어져 있다. 단어 사전에 대한 정보가 모두 주어진 이후에는 빈 줄이 하나 주어진다.

그 다음에는 Boggle 보드의 개수 b가 주어진다. (1 < b < 30) 모든 Boggle은 알파벳 대문자로 이루어져 있고, 4줄에 걸쳐 주어진다. 각 Boggle의 사이에는 빈 줄이 하나  있다.

출력

각각의 Boggle에 대해, 얻을 수 있는 최대 점수, 가장 긴 단어, 찾은 단어의 개수를 출력한다. 한 Boggle에서 같은 단어를 여러 번 찾은 경우에는 한 번만 찾은 것으로 센다. 가장 긴 단어가 여러 개인 경우에는 사전 순으로 앞서는 것을 출력한다. 각 Boggle에 대해서 찾을 수 있는 단어가 적어도 한 개인 경우만 입력으로 주어진다.

풀이

import java.io.*;

class Node {
    boolean isWord;
    boolean isHit;
    Node[] child;

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

    void clearHit() {
        isHit = false;
        for (int i = 0; i < child.length; i++) {
            if(child[i] != null) {
                child[i].clearHit();
            }
        }
    }

    boolean hasChild(char c) {
        return child[c - 'A'] != null;
    }

    Node getChild(char c) {
        return child[c  - 'A'];
    }
}

public class Main {
    static final int GRID_SIZE = 4;
    static final int[] dx = {-1, 1, 0, 0, -1, -1, 1, 1};
    static final int[] dy = {0, 0, -1, 1, -1, 1, -1, 1};
    static final int[] score = {0, 0, 0, 1, 1, 2, 3, 5, 11};
    static BufferedReader br;
    static boolean[][] checked;
    static char[][] grid;
    static Node root;
    static int maxScore, findNum, maxLen;
    static String maxWord;
    static StringBuilder sb, ret;

    public static void main(String[] args) throws IOException {
        init();
        solve();
        System.out.print(ret);
    }

    static void init() throws IOException {
        br = new BufferedReader(new InputStreamReader(System.in));
        sb = new StringBuilder();
        ret = new StringBuilder();
        int n = stoi(br.readLine());
        root = new Node(false, false);

        for (int i = 0; i < n; i++) {
            insert(br.readLine());
        }
        grid = new char[GRID_SIZE][GRID_SIZE];
    }

    static void solve() throws IOException {
        br.readLine();
        int b = stoi(br.readLine());

        //보드의 개수
        for (int i = 0; i < b; i++) {
            if(i != 0) {
                br.readLine();
            }
            //방문 배열 매 보드마다 갱신
            checked = new boolean[GRID_SIZE][GRID_SIZE];
            maxScore = 0;
            maxWord = "";
            findNum = 0;
            maxLen = 0;

            //보드 입력 받기
            for (int j = 0; j < GRID_SIZE; j++) {
                String str = br.readLine();
                for (int k = 0; k < GRID_SIZE; k++) {
                    grid[j][k] = str.charAt(k);
                }
            }

            //0,0부터 3,3까지 찾기
            for (int j = 0; j < GRID_SIZE; j++) {
                for (int k = 0; k < GRID_SIZE; k++) {
                    if(root.hasChild(grid[j][k])) {
                        search(j, k, 1, root.getChild(grid[j][k]));
                    }
                }
            }

            //출력값 입력 및 클리어 히트
            ret.append(maxScore + " " + maxWord + " " + findNum + "\n");
            root.clearHit();
        }
    }

    static void insert(String word) {
        int len = word.length();
        Node cur = root;

        //단어의 문자별로 탐색
        for (int i = 0; i < len; i++) {
            int idx = word.charAt(i) - 'A';

            //없다면 자식 생성
            if(cur.child[idx] == null) {
                cur.child[idx] = new Node(false, false);
            }
            cur = cur.child[idx];
        }

        cur.isWord = true;
    }

    static void search(int x, int y, int depth, Node cur) {
        //체크인
        checked[x][y] = true;
        sb.append(grid[x][y]);
        //목적지인가?
        if(cur.isWord && !cur.isHit) {
            cur.isHit = true;
            //답 작업 -> 최대 길이 단어, 최대 점수, 찾은 단어 개수
            String foundWord = sb.toString();
            int wordLen = sb.length();
            findNum++;
            maxScore += score[wordLen];

            //현재 찾은 단어의 길이가 지금까지 찾은 제일 긴 단어의 길이와 같거나 길 때
            if(wordLen >= maxLen) {
                //같다면 사전 순
                if(wordLen == maxLen) {
                    maxWord = foundWord.compareTo(maxWord) < 0 ? foundWord : maxWord;
                } else {
                    maxWord = foundWord;
                }

                maxLen = wordLen;
            }
        }
        //연결된 곳 순회 : 상, 하, 좌, 우, 대각선 총 8방향
        for (int i = 0; i < 8; i++) {
            int xx = dx[i] + x;
            int yy = dy[i] + y;

            //가능한가?
            //1번 조건 : 맵을 벗어나지 않음
            if(xx < 0 || yy < 0 || xx >= GRID_SIZE || yy >= GRID_SIZE) continue;
            //2번 조건 : 방문하지 않았음
            if(checked[xx][yy]) continue;
            //3번 조건 : 자식 노드가 있음
            if(!cur.hasChild(grid[xx][yy])) continue;
            //간다.
            search(xx, yy, depth+1, cur.getChild(grid[xx][yy]));
        }

        //체크아웃
        checked[x][y] = false;
        sb.deleteCharAt(sb.length() - 1);
    }

    static int stoi(String s) {return Integer.parseInt(s);}
}

내 첫 플레티넘 문제였다 ! 트라이 + dfs 로 풀 수 있었다.

 

삼성 sds 알고리즘 강의에서 트라이 개념을 배우고 이 문제에 구현해보면서 차근차근 풀어봤다. 코드가 길어지다보니 거의 5000B가 나왔다 ㅋㅋㅋ 그래도 이진 트리 개념을 배우면서 어떤 문제를 풀어야할지 감을 조금 잡은거 같아서 다행이다.

 

문제의 순서는 대충 이렇다.

 

1. Trie에 단어 등록

2. 보드판을 생성한다.

3. 보드판의 0,0부터 3,3까지 돈다.

   3-1. 해당 좌표의 문자가 루트 노드와 연결되어 있다면 탐색 시작

4. 탐색은 dfs로 돌며 중복 여부 배열을 통해 왔던 곳을 다시 가지 않도록 한다.

5. Node 객체 안에 isWord, isHit를 각각 넣어줌으로써 현재 위치의 단어가 있는 단어인지, 그리고 이미 맞춘 단어인지 알 수 있다.

6. 사전에 등록된 단어이면서 아직 찾아보지 않은 단어이면 문제에서 요구하는 답을 구해준다. 이 때 더 긴 단어가 있을 수 있으니 탐색을 멈추면 안된다.

7. 목적지가 아니라면 8방향을 보며 3가지 조건에 맞는지 확인 후 맞다면 거기로 간다.

   7-1. 1번째 조건 = 맵을 벗어나지 않는가?

          2번째 조건 = 방문 한적 있는 곳인가?

          3번째 조건 = Trie에서 현재 노드의 자식 노드들 중에 방문 할 위치의 단어가 있는가?