[Python] 백준 9202 Boggle

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

9202번: Boggle

1. 접근 방법

주어지는 알파벳 판에서 등장하는 단어들을 찾아내는 문제로, 알파벳 보드 판에서는 8방향 탐색이 가능하고, 찾아낸 단어들은 총 3가지 출력을 해야 한다.
문자열을 찾는 문제여서 트라이를 활용했다. 주어진 단어를 트라이 구조로 만들어 탐색에 활용했고, 시간을 줄이기 위해 몇 차례 시행착오를 거쳤다.

---

2. 풀이 코드

🖥python 코드 링크 : https://github.com/mintropy/PS/tree/master/BAEKJOON/Python/9000/9200/9202.py

GitHub - mintropy/PS: 다양한 알고리즘 문제 풀이 저장소입니다.

코드 바로보기 :

 

"""
Title : Boggle
Link : https://www.acmicpc.net/problem/9202
"""

from sys import stdin

input = stdin.readline
II = lambda: int(input())
IS = lambda: input().strip()

Vector = tuple[int]


class Node:
    def __init__(self) -> None:
        self.last: bool = False
        self.child: dict = {}

    def add_node(self, string: str) -> None:
        current = self
        for s in string:
            if s not in current.child:
                current.child[s] = Node()
            current = current.child[s]
        current.last = True


def search(x: int, y: int, string: str, node: Node):
    global trie, words_count, delta, boggle_board
    if node.last:
        words_count.add(string)
    visited[x][y] = True
    for dx, dy in delta:
        nx, ny = x + dx, y + dy
        if 0 <= nx < 4 and 0 <= ny < 4:
            if visited[nx][ny]:
                continue
            if (s := boggle_board[nx][ny]) in node.child:
                search(nx, ny, string + s, node.child[s])
                pass
    visited[x][y] = False


if __name__ == "__main__":
    W: int = II()
    trie = Node()
    for _ in range(W):
        string = IS()
        trie.add_node(string)

    words_point: Vector = (0, 0, 0, 1, 1, 2, 3, 5, 11)
    delta: tuple[Vector] = (
        (-1, 0),
        (-1, 1),
        (0, 1),
        (1, 1),
        (1, 0),
        (1, -1),
        (0, -1),
        (-1, -1),
    )
    visited = [[False] * 4 for _ in range(4)]

    input()
    B: int = II()
    ans = ""
    for k in range(B):
        boggle_board: tuple[str] = tuple(IS() for _ in range(4))
        words_count: set[str] = set()
        for i, line in enumerate(boggle_board):
            for j, s in enumerate(line):
                if s in trie.child:
                    search(i, j, s, trie.child[s])

        score: int = 0
        max_len_word = "a"
        for word in words_count:
            score += words_point[len(word)]
            if len(max_len_word) < len(word) or (
                len(max_len_word) == len(word) and max_len_word > word
            ):
                max_len_word = word
        ans += f"{score} {max_len_word} {len(words_count)}\n"
        if k == B - 1:
            break
        input()
    print(ans)

 

📕코드 해설

트라이 구조를 위한 Node클래스, 탐색을 위한 search함수, 그리고 나머지 문제 풀이 로직 부분으로 크게 구분할 수 있다.

class Node:
    def __init__(self) -> None:
        self.last: bool = False
        self.child: dict = {}

    def add_node(self, string: str) -> None:
        current = self
        for s in string:
            if s not in current.child:
                current.child[s] = Node()
            current = current.child[s]
        current.last = True

트라이 구조를 위해서 위의 클래스 하나만 활용했다. 최고 루트 노드부터 각 자식 노드로 내려가는 방향으로 구현했다. 각 점은 어떤 단어의 마지막인지를 나타내는 last와 자식들을 저장하는 child로 구성했다. 그리고 어떤 문자열이 들어오면 앞에서부터 한 알파벳씩 확인하며 추가하고, 문자열의 마지막 알파벳이 추가되었을 때 last에 표시를 한다.

def search(x: int, y: int, string: str, node: Node):
    global trie, words_count, delta, boggle_board
    if node.last:
        words_count.add(string)
    visited[x][y] = True
    for dx, dy in delta:
        nx, ny = x + dx, y + dy
        if 0 <= nx < 4 and 0 <= ny < 4:
            if visited[nx][ny]:
                continue
            if (s := boggle_board[nx][ny]) in node.child:
                search(nx, ny, string + s, node.child[s])
                pass
    visited[x][y] = False

탐색 함수는 다음과 같이 DFS로 구성했다. 우선 어떤 단어의 마지막이라면, 단어를 찾았다는 의미에서 words_count에 추가한다. (자세한 내용은 뒷부분에서 설명) 이후 8방향 탐색을 진행하는데, boggle보드에서 나타나는 어떤 알파벳이 가능한지 기준으로 탐색한다.

ans = ""
for k in range(B):
    boggle_board: tuple[str] = tuple(IS() for _ in range(4))
    words_count: set[str] = set()
    for i, line in enumerate(boggle_board):
        for j, s in enumerate(line):
            if s in trie.child:
                search(i, j, s, trie.child[s])

    score: int = 0
    max_len_word = "a"
    for word in words_count:
        score += words_point[len(word)]
        if len(max_len_word) < len(word) or (
            len(max_len_word) == len(word) and max_len_word > word
        ):
            max_len_word = word
    ans += f"{score} {max_len_word} {len(words_count)}\n"
    if k == B - 1:
        break
    input()
print(ans)

전체 로직을 생성하는 부분이다. 우선 탐색 횟수만큼 for문을 반복하고, 입력을 받는 부분에서 시작한다. 찾을 수 있는 단어들에 대하여 총 3가지 답을 구해야 하는데, 중복 없이 찾는 것이 중요하므로 set을 활용했다. dictionary를 활용하여 각 값 별 True, False로 표시할 수도 있을 것 같다.
이후 모든 위치에서 시작하기 위해 2중 for문을 구성했는데, 여기서 조금 더 성능을 올리기 위해 enumerate를 사용했다.
정답을 구하고 출력하는 부분은 뒷부분에서 설명하겠지만, 여러 차례 고민을 했다. 결과적으로 지금의 코드는 출력은 한 번에 모아서 하고, 정답을 구할 때는 한 번의 순회를 진행한다. 출력 중에 가장 긴 단어, 그러한 단어가 많으면 사전 순으로 빠른 단어를 출력하라는 부분이 있다. 이 부분을 해결하기 위해 처음에 소문자 a를 두고 시작했다. 그 이유는 적어도 입력 단어의 길이는 한 자 이상이고, 입력이 대문자이면 소문자는 항상 더 늦은 순서로 되기 때문이다. (하지만 길이도 고려하기 때문에 빈 문자열로 시작해도 무방하다.)

troubleshooting

여러 차례 문제를 풀며 고민했던 부분들을 정리했습니다.

출력하는 정답 단어

여기서 많이 헤매었다. 출력해야 하는 단어는, Boggle에서 발견할 수 있는 단어이면서, 가장 긴 단어, 그중에서 사전 순으로 가장 앞서는 것을 출력해야 한다. list.sort()를 사용한다면 정렬 key로 길이 내림차순, 알파벳 오름차순 정렬을 하도록 지정해야 하고, 아니라면 그냥 for문을 순회하며 각 단어를 순서대로 비교할 수도 있다.

시간 줄이기 1

시간을 줄이기 위해 출력을 하나의 문자열에 저장, 이후에 출력하는 방식으로 진행했다. 결과는 위의 코드에서 확인할 수 있고, 이전에는 ans에 더하는 과정 대신 바로 출력하는 방식으로 진행했다.

• 31320ms → 27372ms (PyPy)

시간 줄이기 2

처음에는 딕셔너리 하나에 모든 키와 값을 추가하는 방식으로 진행했다. 만약 각 값에 다시 키를 저장하는 방식으로 구현했다면 더욱 효율적이었을 수 있지만, 대신 코드를 지금 작성한 것처럼 트라이를 클래스로 구현하는 방식을 선택했다.

• 27372ms→ 21256ms (PyPy)

시간 줄이기 3, Python통과

위의 과정까지는 모두 PyPy로만 통과했다. 무엇이 문제일지 고민했고, 어떤 부분에서 시간을 줄일 수 있을지 고민했다. 가장 윗부분에서 작성한 출력하는 정답 단어 찾는 과정에서 정렬을 활용했는데, 주어지는 보드의 수는 최대 29개이지만, 단어는 30만 개 까지 나올 수 있으므로 정렬에 사용하는 시간이 엄청나게 늘어난다. 정렬하는 대신 한 번 순회하며 값을 비교 & 저장 및 출력하는 방식(지금의 코드에서 진행항 방식)으로 바꾸었다.

• 21256ms → 9280ms (PyPy), 24092ms (Python)

---

3. 생각 정리

트라이 구조를 사용하는데 익숙해지고, 또 한편으로 트라이 구조로 접근하는 게 최선이라고 생각하다 보니 어쩌면 더 쉬운 풀이법을 나 두고 더 복잡하고 어렵게 접근하는 것이 아닐까라는 생각도 들었다.

또 한편으로, 트라이 구조를 응용하는 이런 문제를 더 잘 풀어가는 것도 고민이 된다.