오늘 살펴볼 문제는 백준 9202번 <Boggle> 문제이다.
https://www.acmicpc.net/problem/9202
9202번: Boggle
문제 상근이는 보드 게임 "Boggle"을 엄청나게 좋아한다. Boggle은 글자가 쓰여 있는 주사위로 이루어진 4×4 크기의 그리드에서 최대한 많은 단어를 찾는 게임이다. 상근이는 한 번도 부인을 Boggle로 이겨본 적이 없다. 이렇게 질 때마다 상근이는 쓰레기 버리기, 설거지와 같은 일을 해야 한다. 이제 상근이는 프로그램을 작성해서 부인을 이겨보려고 한다. Boggle에서 단어는 인접한 글자(가로, 세로, 대각선)를 이용해서 만들 수 있다. 하지
www.acmicpc.net
사실 이 문제는 굉장히 어려웠다. 그래서 나는 다른 분의 코드를 어느정도 참고해서 풀었다. 트라이(Trie)라는 자료구조를 써야 하며, DFS로 완전 탐색을 진행한다. 단어의 수가 300,000개여서 시간 복잡도를 철저하게 계산해서 풀어야 제한 시간 안에 풀 수가 있다.
먼저 트라이 자료구조에 대해서 설명을 하고 문제를 풀어보도록 하겠다.
트라이는 문자열이 여러 개가 있을 때 특정 문자열이 있는지를 빠르게 찾는 자료구조이다.
길이가 M 이하인 문자열 N개가 있다고 생각해 보자. 이 문자열 중에서 특정 문자열이 있는지를 찾으려면 시간이 얼마나 걸릴까? 아래처럼 문자열을 처음부터 하나씩 순차적으로 탐색을 하면 O(M*N)이 걸릴 것이다.
N,M이 큰 경우 이러한 방식은 시간이 굉장히 오래 걸린다. 그래서 우리는 트라이를 사용하여 O(M)으로 특정 문자열을 찾는 방법을 알아본다. 문자열 { "dog", "cat", "doggy", "catty", "cate" } 이 있다고 생각해 보자. 처음에 root Node를 설정하고 문자열을 하나씩 받는데, 각각의 문자열을 하나의 문자씩 쪼개서 트리 형태로 저장한다.
이런 트라이 자료구조로 문자열들을 저장하면 위에서 말한 조건에서 O(M)의 시간복잡도를 가지고 원하는 문자열을 찾을 수 있다.
문제로 돌아와서 살펴보자. 처음에 단어 사전에 들어가는 단어들을 트라이에 모두 넣는다. 자바에서 Trie 클래스와 Trie를 구성하는 각각의 Node는 클래스를 따로 만들어 주었다.
트라이에 단어 사전에 들어가는 문자열을 모두 넣은 뒤에는 Boggle 보드를 하나씩 입력받는다. 4X4 문자 타입 배열으로 값을 받은 뒤에 가능한 문자열의 길이인 1~8개에 대해서 각각 DFS를 수행한다. 참고로 여기서는 가로, 세로, 대각선으로 모두 뻗어 나아갈 수 있다.
그리고 DFS로 탐색을 하다가 단어 사전에 있는 단어를 찾으면 HashSet에 넣어준다. Set을 사용하는 이유는 중복을 피하기 위해서이다.
hashSet에 해당 보드에서 만들어질 수 있는 모든 단어가 들어가면 그 다음에 최대 점수, 최장 길이 단어, 전체 단어 갯수를 각각 result() 메서드로 계산한 후 출력하면 된다.
아래는 내가 제출한 자바 소스 코드이다.
트라이 자료구조를 공부하기 좋은 문제인 것 같다. 코드를 천천히 보면서 이해하다보면 많은 것을 배울 수 있는 문제였던 것 같다.
참고자료
'Computer Sci. > Algorithms' 카테고리의 다른 글
| 백준 3176 / LCA 알고리즘, DP, DFS / JAVA (1) | 2020.05.20 |
|---|---|
| 카카오 19겨울인턴 4번 / 유니온 파인드(Union Find) / JAVA (0) | 2020.05.11 |
| 백준 1300 / 이분 탐색 (Binary Search) / JAVA (0) | 2020.05.07 |
| 백준 10422 / 동적 계획법 (Dynamic Programming) / JAVA (0) | 2020.05.05 |
| 백준 2109 / 그리디(Greedy) 알고리즘 / JAVA (1) | 2020.04.30 |
