[BOJ] 9202 Boggle - Java

 

1. 문제 링크

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

---

2. 문제 풀이

 생각보다 플래티넘 V 정도의 문제들은 정석적인 풀이가 아닌 다른 방식으로도 풀리는 경우가 있는 것 같습니다. 이번 문제도 [BOJ] 14942 개미 문제와 같이 DFS로 풀렸습니다. 입력으로 단어들이 300,000 미만 정도의 개수로 주어지는데, 솔직히 시간제한과 메모리 제한이 각각 10초와 512 MB로 매우 널널합니다. 저는 트라이(Trie)와 DFS를 사용한 풀이보다는 Set을 활용한 DFS를 채택하였습니다. HashSet에 모든 단어를 저장한 후, DFS를 통해 단어의 존재 여부를 확인하며 문제를 해결했습니다. 이렇게 구현한 이유는 HashSet의 탐색 속도가 평균적으로 O(1)에 가깝고, 단어 길이가 짧아 Trie의 구조적 이점이 크지 않다고 판단했기 때문입니다.

 

 

Set<String> set = new HashSet<>();
for(int i = 0; i < w; i++) set.add(br.readLine());

Set으로 단어 사전을 만들었지만, 그래도 Trie로 단어 사전을 어떻게 만들 수 있는지도 알고 넘어가면 좋겠죠? Trie는 기본적으로 단어 사전, 문자열 검색, 접두사(prefix) 검색 문제를 풀 때 사용하는 방식입니다. 근데 왜 Trie냐고요? retrieval에서 유래된 이름이에요.

 

일단, 단어가 {cat, car, care, day, data} 배열로 주어진다고 생각해 봅시다. 이 데이터들을 어떻게 다루어야 효율적으로 잘 만들었다고 소문이 날까. 트리 구조가 떠오를 겁니다. 문자를 하나씩 떼어내서 잘 배치하면 되겠죠? 근데 루트 노드는 어떻게 선정할까요?

 

Trie 구조

아이패드가 없어서 마우스로 대충 그렸습니다. 루트 노드는 비워둡니다. 각 노드는 문자를 나타내고 있고, 문자열의 끝에는 End-Of-Word 표시를 해두는 형태입니다. 문자열의 삽입과 탐색에 있어서는 O(문자열의 길이)의 시간 복잡도를 가집니다. 그림으로 보니까 뭔가뭔가죠? 공통 접두사를 공유하는 경우에 효율적입니다. 다만, 그렇지 않은 희소한 데이터들로만 구성되어 있다면 오히려 메모리만 낭비하게 되겠죠.

 

아무튼 이런 방식으로 접두사를 통해 검색어 자동완성과 같은 기능을 만들 수도 있겠습니다.

 

Trie를 연습하기 좋아 보이는 문제들이 있어서 저번 포스트처럼 추천 문제를 남겨놓고.. 나중에 천천히 풀어보면 좋을 것 같습니다.

 

[Trie 연습 문제]

Silver : 4358 생태학 / 14425 문자열 집합

Gold : 5052 전화번호 목록 / 14725 개미굴 / 20166 문자열 지옥에 빠진 호석

Platinum : 5446 용량 부족 / 5670 휴대폰 자판 / 19585 전설

 

 

while((str = br.readLine()) != null){
    if(str.isEmpty()) continue;
    board[idx/4][idx%4] = str.toCharArray();
    idx++;
    if(b <= (idx/4)) break;
}

 백준에서 입력에 대해 좀 애매하게 명시되어 있으면 while문으로 null 체크를 하고 진행하는 편입니다. 이번 문제에서는 굳이 그럴 필요는 없었지만 습관이란.. 아래쪽에 있는 조건을 변형시켜 while 조건에 넣었어도 좋았을 듯합니다.

 

이후로는 DFS를 진행하면서 추가로 생성한 Set에서 중복 필터링을 해주었습니다. 일반적인 DFS라 별다른 설명은 필요 없을 듯! 하단에 첨부한 소스 코드에서 확인하면 되겠습니다.

---

3. 소스 코드

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

public class Main {
    static Set<String> set = new HashSet<>();
    static char[][][] board;
    static Set<String> tmpSet;
    static boolean[][] visited;
    static int score; static String longestWord;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String str = br.readLine();
        int w = Integer.parseInt(str);
        for(int i = 0; i < w; i++) set.add(br.readLine());
        br.readLine();
        int b = Integer.parseInt(br.readLine()), idx = 0;
        board = new char[b][4][4];
        while((str = br.readLine()) != null){
            if(str.isEmpty()) continue;
            board[idx/4][idx%4] = str.toCharArray();
            idx++;
            if(b <= (idx/4)) break;
        }
        for(int i = 0; i < b; i++){
            tmpSet = new HashSet<>();
            visited = new boolean[4][4];
            score = 0; longestWord = "";
            for(int x = 0; x < 4; x++) {
                for(int y = 0; y < 4; y++) {
                    visited[x][y] = true;
                    StringBuilder sb = new StringBuilder();
                    sb.append(board[i][x][y]);
                    dfs(i, x, y, sb);
                    visited[x][y] = false;
                    sb.deleteCharAt(sb.length()-1);
                }
            }
            System.out.println(score + " " + longestWord + " " + tmpSet.size());
        }
    }
    static int[] dx = {-1, -1, -1, 0, 0, 1, 1, 1};
    static int[] dy = {-1, 0, 1, -1, 1, -1, 0, 1};
    static void dfs(int bn, int x, int y, StringBuilder sb){
        if(sb.length() == 8){
            return;
        }
        for(int i = 0; i < 8; i++){
            int nx = x + dx[i];
            int ny = y + dy[i];
            if(0 <= nx && nx < 4 && 0 <= ny && ny < 4){
                if(!visited[nx][ny]){
                    visited[nx][ny] = true;
                    sb.append(board[bn][nx][ny]);
                    String tmp = String.valueOf(sb);
                    if(set.contains(tmp) && !tmpSet.contains(tmp)){
                        int tmpLen = tmp.length();
                        switch(tmpLen){
                            case 3: case 4:
                                score++;
                                break;
                            case 5:
                                score+=2;
                                break;
                            case 6:
                                score+=3;
                                break;
                            case 7:
                                score+=5;
                                break;
                            case 8:
                                score+=11;
                                break;
                        }
                        if(longestWord.length() < tmpLen) longestWord = tmp;
                        else if(longestWord.length() == tmpLen){
                            int diff = longestWord.compareTo(tmp);
                            if(0 < diff) longestWord = tmp;
                        }
                        tmpSet.add(tmp);
                    }
                    dfs(bn, nx, ny, sb);
                    visited[nx][ny] = false;
                    sb.deleteCharAt(sb.length()-1);
                }
            }
        }
    }
}

---

4. 한줄평

Trie에 대한 답이 본인에게 중요한 것임을 확인받을 수 있는지를 정확히 이야기해주십사 감찰해주실 수 있는지를 알렸을때 이상이 없는지에 대해 거북하게 느끼시지는 않는지가 옳은 일인지를 발설해도 될지에 대하여 의문이 존재함을 표현해도 되는지에 대해 인지할 자격이 본인에게 있는지를 여쭤봐도 되겠습니까?