•
문제 설명
Boggle이라는 보드 게임이 있습니다. 글자가 쓰여 있는 주사위로 이루어진 4x4 크기의 그리드에서 최대한 많은 단어를 찾는 게임입니다. 글자수 마다 점수가 주어져있습니다. 단어 사전에 등재되어 있는 단어의 목록과 Boggle 게임 보드가 주어졌을 때, 얻을 수 있는 최대 점수, 가장 긴 단어, 찾은 단어의 수를 구하는 프로그램을 작성하는 것이 목표입니다.
•
입력
첫째 줄에 단어 사전에 들어있는 단어의 수 w가 주어진다. (1 < w < 300,000) 다음 w개 줄에는 단어가 주어진다. 단어는 최대 8글자이고, 알파벳 대문자로만 이루어져 있다. 단어 사전에 대한 정보가 모두 주어진 이후에는 빈 줄이 하나 주어진다.
그 다음에는 Boggle 보드의 개수 b가 주어진다. (1 < b < 30) 모든 Boggle은 알파벳 대문자로 이루어져 있고, 4줄에 걸쳐 주어진다. 각 Boggle의 사이에는 빈 줄이 하나 있다.
•
출력
각각의 Boggle에 대해, 얻을 수 있는 최대 점수, 가장 긴 단어, 찾은 단어의 개수를 출력한다. 한 Boggle에서 같은 단어를 여러 번 찾은 경우에는 한 번만 찾은 것으로 센다. 가장 긴 단어가 여러 개인 경우에는 사전 순으로 앞서는 것을 출력한다. 각 Boggle에 대해서 찾을 수 있는 단어가 적어도 한 개인 경우만 입력으로 주어진다.
•
풀이
단어 사전이 주어지면 해당 단어들을 트라이로 만들어 저장하고, Boggle을 dfs로 만들어 질 수 있는 모든 단어들을 트라이에서 검색하여 찾습니다. 트라이에서 해당 단어를 찾을 때 조금 생각해야 하는 부분이 있습니다.
예를 들어, Boggle에서 현재 찾은 단어가 AB이고, Trie에 ABC가 저장되어 있다고 가정한다면 현재 찾은 단어는 유망한 단어, 즉 앞으로 C가 더 나온다면 단어 사전에 등재된 단어를 찾는 것이기 때문에 dfs탐색을 멈추지 않고 더 깊이 탐색하게 됩니다.
또 생각해 볼 문제가 있는데, "Boggle에 대해서 찾을 수 있는 단어가 적어도 한 개인 경우만 입력으로 주어진다."라고 했기 때문에 찾은 단어들은 겹치면 안된다는 문제가 있습니다. 겹치면 안된다는 것에서 바로 Set자료 구조를 떠올릴 수 있지만, 저는 Trie의 특성 중에서 terminal이 true이면 해당 노드에 적절한 표시를 통해 이미 찾은 단어임을 알 수 있다는 것을 이용하였습니다.
•
코드
•
개인적인 총평
트라이 자료구조에 대한 깊은 이해를 할 수 있었고 그 이해를 바탕으로 코드로 녹여낼 수 있었다는 생각이 듭니다. 항상 어렵다고 미뤄왔던 자료구조인데, 이번 기회를 통해 확실히 정리하고 넘어가는 것 같아서 좋았습니다. 이번에 푼 문제는 오히려 DFS 부분에 방문 처리를 해제하는 부분에서 발생한 문제 때문에 고생을 했는데, 생각보다 코드에 어떤 부분에서 오류가 발생한 것인지 찾기가 어려웠습니다. 해결 방안은 코드를 충분히 모듈화 하여 어느 부분이 잘못된 것인지에 대한 확인이 빠르게 이루어지게 하는 것이 있다고 생각합니다. 예외케이스를 찾기가 굉장히 어려웠고, 그 예외케이스는 제 코드에 대한 부정확한 이해도에서 왔습니다. 조금 더 코드를 고민하면서 작성해야겠다는 생각이 들었습니다.
