[Python] 백준 9202번: Boggle

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

9202번: Boggle

 

import sys
input = sys.stdin.readline
dx = [-1, -1, -1, 0, 1, 1, 1, 0]
dy = [-1, 0, 1, 1, 1, 0, -1, -1]

POINTS = [0, 0, 0, 1, 1, 2, 3, 5, 11]
LENGTH = 4


class Node:
    def __init__(self):
        self.children = {}
        self.is_ended = False


class Trie:
    def __init__(self):
        self.root = Node()

    def insert(self, word):
        current_node = self.root

        for c in word:
            if not current_node.children.get(c):
                current_node.children[c] = Node()

            current_node = current_node.children[c]

        current_node.is_ended = True

    def search(self, current_node, x, y, current_word):
        is_visited[x][y] = True

        # 단어가 처음 발견되었을 때
        if current_node.is_ended and (not current_word in found_nodes):
            global point, largest_word, word_count

            # 가장 긴 단어 갱신
            if len(largest_word) < len(current_word):
                largest_word = current_word
            elif len(largest_word) == len(current_word):
                # 사전순
                if largest_word > current_word:
                    largest_word = current_word

            point += POINTS[len(current_word)]
            word_count += 1

            found_nodes.add(current_word)

        # 탐색
        for i in range(8):
            nextX, nextY = x + dx[i], y + dy[i]
            if (0 <= nextX <= LENGTH-1 and 0 <= nextY <= LENGTH-1) and is_visited[nextX][nextY] == False:
                n = grid[nextX][nextY]
                if current_node.children.get(n):
                    self.search(
                        current_node.children[n], nextX, nextY, current_word+n)

        is_visited[x][y] = False


if __name__ == '__main__':
    trie = Trie()
    is_visited = [[False]*LENGTH for _ in range(LENGTH)]

    w = int(input())
    for _ in range(w):
        trie.insert(str(input().rstrip()))
    _ = input()

    b = int(input())
    for i in range(b):
        grid = [str(input().rstrip()) for _ in range(LENGTH)]
        if i != b-1:
            _ = input()

        # 초기화
        found_nodes = set()
        point = 0
        largest_word = ""
        word_count = 0

        # 현재 grid에 대해 탐색
        for x in range(LENGTH):
            for y in range(LENGTH):
                c = grid[x][y]
                if trie.root.children.get(c):
                    trie.search(trie.root.children[c], x, y, c)

        # 출력
        print(point, largest_word, word_count)

 

구현이 너무 복잡한 문제였다. Trie + DFS + Backtracking이 동시에 쓰인 문제이다. 이 글은 Trie를 알고 있다는 전제 하에 작성하였다.

 

개인적으로 글만으로는 Boggle Game이 대체 무슨 게임인지(특히 주사위가 왜 있는지 이해가 안 됐었다.) 도통 이해가 안 돼서 구글링으로 이미지를 보고 감을 잡았었다.

 

먼저 '사전에 있는 단어'는 Trie의 insert로 자리를 채워주는 것까진 너무나도 뻔하다. 하지만 탐색이 문제다.

 

탐색은 앞서 말했듯이 DFS이며, 여기서 문제의 조건에 의해 신경써주어야할 부분들은 다음과 같다.

 - Trie의 노드를 순차적으로 탐색하는 식으로 DFS가 진행되어야 한다.

 - 단어의 중복을 허용하지 않는다.(found_nodes에 이미 찾은 단어들을 저장하여 해결하였다.)

 - 가장 긴 단어를 출력해야하며, 만약 길이가 같은 단어들이 있을 경우에는 사전순으로 앞선 것을 출력한다.

 - 중복된 방문을 허용하지 않는다.(is_visited)

 

아래는 내가 이 문제를 푸는 데 도움이 되었던 케이스들이다.

2
ABCDX
ABCDXX

1
ABCD
XXXX
XXXX
XXXX

1
A

1
ABCD
XXXX
XXXX
XXXX