BOJ 9202

Boggle

풀이 접근

이 문제는 트라이 자료구조로 풀이할 수 있다.

풀이법 1(시간초과)

1. 사전(dictionary)의 단어에 대해 트라이를 초기화한다.
2. DFS 탐색
   • 지금까지 방문한 단어의 순서로 만들어진 문자열(l)이 트라이에 있는지 확인
   • l로 시작하는 단어가 트라이에 없으면 DFS 종료(최적화)
3. 트라이에 조회된 단어 저장

트라이 구현

트라이가 뭐지?

트라이

트라이 구현

class TrieNode:
    def __init__(self, character=None):
        self.c = character
        self.children = {}
        self.is_end = False # 이 글자가 마지막인 문자열이 존재함을 나타내는 Flag
 
class Trie:
    def __init__(self):
        self.head = TrieNode()
 
    def add(self, string):
        if len(string) == 0:
            return
        current = self.head
        for c in string:
            if c not in current.children:
                current.children[c] = TrieNode(c)
            current = current.children[c]
        current.is_end = True
    
    def search(self, string):
        current = self.head
        for c in string:
            if c not in current.children:
                return False
            current = current.children[c]
        return current.is_end
 
    def is_prefix(self, string):
        current = self.head
        for c in string:
            if c not in current.children:
                return False
            current = current.children[c]
        return True

전역 변수와 로직 흐름

dx = [-1, -1, 0, 1, 1, 1, 0, -1]
dy = [0, 1, 1, 1, 0, -1, -1, -1]
board = list() # 이차원 리스트
found = set() # 보드에서 발견한 문자열 집합
visited = [[False for _ in range(4)] for _ in range(4)]
 
# 로직 흐름
# 트라이 초기화
trie = Trie()
for _ in range(int(input())):
    trie.add(input().strip())
input()
 
# 보드별 정답 구하기
n = int(input())
for i in range(n):
    board = [list(input().strip()) for _ in range(4)]
    found = set()
    visited = [[False for _ in range(4)] for _ in range(4)]
    play_game()
    if i != n - 1:
        input()

출력 데이터를 구하는 로직 흐름

def play_game():
    global found
    scores = 0
    find_word() # 해당 보드에서 얻을 수 있는 단어 찾기
    found = list(found) # 정렬을 위해 집합을 리스트로 변환
    found.sort(key= lambda w: (-len(w), w))
    
    for word in found:
        scores += get_score(word)
    print(scores, found[0], len(found))
    return

DFS 탐색으로 트라이 조회

# DFS
def find(x, y, chars: list): # chars: 현재까지 순서대로 방문한 알파벳 리스트
    # 길이 초과시
    if len(chars) > 8:
        return
        
    # 사전에 있는 단어인지 확인
    target = ''.join(chars)
 
	# 존재하지 않는 prefix면 DFS 종료
    if not trie.is_prefix(target):
        return
 
	# 존재하는 단어 저장
    if trie.search(target):
        found.add(target)
 
    for i in range(8):
        nx, ny = x + dx[i], y + dy[i]
        if is_range(nx, ny) and not visited[nx][ny]:
            visited[nx][ny] = True
            chars.append(board[nx][ny])
            find(nx, ny, chars)
            visited[nx][ny] = False
            chars.pop()
            
    
 
def find_word() -> None:
    for i in range(4):
        for j in range(4):
            visited[i][j] = True
            find(i, j, [board[i][j]])
            visited[i][j] = False
    return

풀이법2(트라이 조회 최적화)

매 DFS마다 prefix와 search를 수행하는 것이 비효율적이다.

그럼 어떻게 해결할까? 트라이 노드의 is_end(이 글자가 마지막인 문자열이 존재함을 나타내는 Flag) 를 활용하면 최적화할 수 있다.

1. 루트에서 해당 글자를 가진 children이 있는지 확인
2. 재귀: 현재 트라이 노드에서 다음 글자로 이동할 수 있는지 확인
   1. 만약 자식이 없으면(prefix가 아니면) 탐색 종료
   2. 현재 노드의 is_end 가 True이면, 단어 저장

최종 코드

Boggle Boggle

class TrieNode:
    def __init__(self, character=None):
        self.c = character
        self.children = {}
        self.is_end = False
 
class Trie:
    def __init__(self):
        self.head = TrieNode()
 
    def add(self, string):
        if len(string) == 0:
            return
        current = self.head
        for c in string:
            if c not in current.children:
                current.children[c] = TrieNode(c)
            current = current.children[c]
        current.is_end = True
 
import sys
 
input = sys.stdin.readline
dx = [-1, -1, 0, 1, 1, 1, 0, -1]
dy = [0, 1, 1, 1, 0, -1, -1, -1]
board = list() # 이차원 리스트
found = set() # 보드에서 발견한 문자열
visited = [[False for _ in range(4)] for _ in range(4)]
 
def get_score(string: str):
    length = len(string)
    if length <= 2:
        return 0
    elif length <= 4:
        return 1
    elif length == 5:
        return 2
    elif length == 6:
        return 3
    elif length == 7:
        return 5
    return 11
 
def is_range(x, y):
    return 0 <= x < 4 and 0 <= y < 4
 
# DFS
def find(x, y, node, word):
    if node.is_end:
        found.add(word)
 
    # 길이 초과시
    if len(word) >= 8:
        return
 
    for i in range(8):
        nx, ny = x + dx[i], y + dy[i]
        if is_range(nx, ny) and not visited[nx][ny]:
            c = board[nx][ny]
            # 해당 글자가 자식 노드로 존재하면 탐색 진행
            if c in node.children:
                visited[nx][ny] = True
                find(nx, ny, node.children[c], word + c)
                visited[nx][ny] = False
            
def find_word() -> None:        
    for i in range(4):
        for j in range(4):
            c = board[i][j]
            # 해당 글자가 자식 노드로 존재하면 탐색 진행
            if c in trie.head.children:
                visited[i][j] = True
                find(i, j, trie.head.children[c], c)
                visited[i][j] = False
 
def play_game():
    global found
    scores = 0
    find_word()
    found = list(found)
    found.sort(key= lambda w: (-len(w), w))
    for word in found:
        scores += get_score(word)
    print(scores, found[0], len(found))
 
trie = Trie()
for _ in range(int(input())):
    trie.add(input().strip())
input()
 
n = int(input())
for i in range(n):
    board = [list(input().strip()) for _ in range(4)]
    found = set()
    visited = [[False for _ in range(4)] for _ in range(4)]
    play_game()
    if i != n - 1:
        input()