[백준/Java] 9202 Boggle

🔗 문제 링크: https://www.acmicpc.net/problem/9202

 

🔍 해결 과정

이 문제를 간단히 요약하자면 최대 30만 값을 가진 w개의 단어 사전들이 존재하는데 최대 29번의 boggle을 진행해서 각 경우마다 단어사전에 해당하는 단어들을 찾은 다음 문제의 요구에 맞게 정답을 출력하면 되는 문제입니다.

 

w의 최댓값이 30만이라는 점에서 시간복잡도를 최적화해야겠다는 생각이 들었지만, boggle 보드판의 크기는 4x4이고, 단어의 길이도 최대 8이라는 점을 감안했을 때 dfs와 가지치기(pruning)를 활용하여 백트래킹 기법을 사용해 시간 안에 문제를 해결할 수 있습니다. (참고로 문제에서 요구하는 최대 시간은 10초입니다.) 또한 단어 사전에 들어있는 단어의 개수가 최대 30만개이므로 단순 배열을 통해서 해당 단어를 찾기에는 많은 시간이 소요될 수 있어 Java의 HashMap 자료구조를 활용하였습니다. 이로써 단어 사전을 살펴봤는지 확인할 때 시간복잡도를 O(1)로 줄일 수가 있습니다.

 

코드의 과정을 요약하면 다음과 같습니다.

1️⃣ HashMap 자료구조인 dics 변수를 만들어 단어 사전을 살폈는지 확인하는 용도로 활용한다.
2️⃣ List<String> finds를 통해서 boggle에서 등장한 단어 사전의 내용을 저장하는 용도로 활용한다.
3️⃣ boggle 보드판을 돌면서 시작지점에 의해서 나올 수 있는 단어의 경우를 전부 살펴보며 단어 사전에 나온 단어들을 저장한다.
4️⃣ 단어를 전부 찾았으면 문제에서 요구하는 조건에 맞게 finds의 단어 내용들을 정렬하고 정답을 출력한다.

 

---

✏️ 코드

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

public class Main {

    private static int[] dx = {-1, 1, 0, 0, -1, -1, 1, 1}; // 상하좌우 대각(위좌, 위우, 우아,왼아)
    private static int[] dy = {0, 0, -1, 1, -1, 1, 1, -1};
    private static Map<String, Integer> dics;
    private static Map<Integer, Integer> scores;
    private static List<String> finds;
    private static StringBuilder result;
    private static int maxScore = 0;


    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringBuilder sb = new StringBuilder();
		int w = Integer.parseInt(br.readLine()); // 단어 사전에 들어 있는 단어의 수 (30만)
        dics = new HashMap<>(); // 단어 사전, 나온 횟수
        scores = new HashMap<>(); // 단어의 길이, 점수
        scores.put(1, 0);
        scores.put(2, 0);
        scores.put(3, 1);
        scores.put(4, 1);
        scores.put(5, 2);
        scores.put(6, 3);
        scores.put(7, 5);
        scores.put(8, 11); // 글자 길이에 대한 점수 정보 입력하기

        for (int i = 0; i < w; ++i) { // 단어 사전에 들어있는 단어의 정보
            dics.put(br.readLine(), 0); // 처음엔 0개가 나옴
        }

        // 줄바꿈 하나 입력을 받음
        br.readLine();

        // 보드의 개수 (4 x 4)
        int b = Integer.parseInt(br.readLine());

        for (int bc = 0; bc < b; ++bc) {
            // 보드판의 정보를 입력받기
            char[][] boggle = new char[4][4];
            result = new StringBuilder();
            finds = new ArrayList<>(); // 찾은 단어를 넣어두기 위함

            for (int i = 0; i < 4; ++i) {
                boggle[i] = br.readLine().toCharArray(); // 보드판으로 만들기
            } // 보드판 만들기 완료

            // dfs를 통해서 모든 단어를 찾아내기
            for (int i = 0; i < 4; ++i) {
                for (int j = 0; j < 4; ++j) {
                    // 얻을 수 있는 최대 점수, 가장 긴 단어, 찾은 단어의 개수
                    dfs(boggle, new boolean[4][4], new StringBuilder(), i, j, 1);
                }
            }

            // 여기서 finds 처리해주기 (가잔 긴 단어 순으로 내림차순 정렬, )
            int wordCount = finds.size(); // 찾은 단어의 개수

            Collections.sort(finds, (a, c) ->  {
                if (c.length() == a.length()) { // 길이가 같으면 사전 순 정렬
                    return a.compareTo(c);
                }

                return c.length() - a.length();
            });

            String maxWord = finds.get(0);

            // 점수 계산하기
            int score = 0;
            for (String f : finds) {
                score += scores.get(f.length());
            }

            sb.append(score).append(" ").append(maxWord).append(" ").append(wordCount).append("\n");

            for (Map.Entry<String, Integer> entry : dics.entrySet()) {
                dics.put(entry.getKey(), 0);
            }

            if (bc < b - 1) {
                br.readLine();  // 줄바꿈 처리
            }
        }

        bw.write(sb.toString());
        bw.flush();
    }

    private static void dfs(char[][] boggle, boolean[][] visited, StringBuilder sb,
                            int x, int y, int step) {
        visited[x][y] = true;
        sb.append(boggle[x][y]);

        // 현재 dics에서 단어가 존재하는지 확인하기
        if (dics.getOrDefault(sb.toString(), -1) == 0) { // 존재 하고, 안 살펴봤다면
            // 단어를 담아주기
            finds.add(sb.toString());
            dics.put(sb.toString(), 1); // 찾았으므로 살펴봤다는 표시해두기
        }

        if (step == 8) { // 최대 8글자임. 다 살펴본 것임
            visited[x][y] = false; // 다음 단어 살피기 위해 원상태로 돌려놓음
            sb.deleteCharAt(sb.length() - 1);
            return;
        }

        for (int dir = 0; dir < 8; ++dir) {
            int nx = x + dx[dir];
            int ny = y + dy[dir];

            if (nx < 0 || ny < 0 || nx >= 4 || ny >= 4) {
                continue;
            }

            if (visited[nx][ny]) {
                continue;
            }

            dfs(boggle, visited, sb, nx, ny, step + 1);
        }

        visited[x][y] = false; // 다음 단어를 살펴보기 위해 다시 원상태로 돌려놓음
        sb.deleteCharAt(sb.length() - 1);
    }
}