백준[9202] Boggle (Python3)

그래프를 이용해 푸는 트라이 문제
신경써야 할 부분이 중간중간 있기 때문에 한번 논리가 꼬이면 고생한다.

지문 분석

현재 이동한 곳의 경로가 사전에 등록된 단어가 될 수는 없지만, 돌아서 가는 경우 등록된 단어일 수있다.
예를 들자면 현재 주사위에 다음과 같이 써져있다 하고 사전에 등록된 단어는 CDBA라 하자.

AB
CD

C에서 탐색을 시작한다 할 때, 바로 A로 가면 사전에 등록된 단어가 되지 않지만, C->D->B->A 순으로 가면 사전에 등록된 단어가 된다.

 

따라서 bfs로 하기엔 각 큐마다 방문 상태를 별개로 저장해야 하는 불편함이 있었고, 범위가 4*4 였던 점을 이용해 백트래킹을 사용했다.

 

또한, 사전에 등록된 한 단어에 도달하는 과정에서 다른 단어들을 충족한 경우 이 단어들도 같이 계산해줬다. 그 이유는, 지문에서 최대한 많은 단어를 찾는다고 했기 때문이다.

예를 들자면, 사전에 등록된 단어가 AA, AAA이고 주사위에 AAA 가 있다면, 둘다 찾은걸로 친다.

이제 다음 탐색을 하는 과정에서 다음 경우를 고려한다.

1. 방문할 곳에 있는 단어가 현재 딕셔너리에 있는지
2. 현재 딕셔너리에 마지막을 뜻하는 문자가 있다면, 현재 경로를 통해 만들어진 문자열을 이미 찾은 이력이 있는지(set 사용해서 체크했음)

본래라면 평범한 골드급 그래프 탐색 문제였지만, 트라이 알고리즘이 기본적으로 티어가 높아서 그런지 플래 5로 지정된 거 같다.

 

class Trie:
    def __init__(self):
        self.root = {}
        self.dir = [[1, 0], [1, 1], [1, -1], [-1, 0], [-1, 1], [-1, -1], [0, 1], [0, -1]]
        self.score = [0, 0, 0, 1, 1, 2, 3, 5, 11]
        self.board = []
        self.visit = [[False for _ in range(4)] for _ in range(4)]
        self.total = 0
        self.find_sentence = ""
        self.found = set()

    def insert(self, S):
        current_node = self.root
        for s in S:
            if s not in current_node:
                current_node[s] = {}
            current_node = current_node[s]
        current_node[0] = True

    def search(self, here_y, here_x, here_s, here_node):
        if 0 in here_node:
            S = "".join(here_s)
            if S not in self.found:
                self.found.add(S)
                self.total += self.score[len(S)]
            self.find_sentence = S
        for d in self.dir:
            there_y, there_x = here_y + d[0], here_x + d[1]
            if there_y < 0 or there_y >= 4 or there_x < 0 or there_x >= 4:
                continue
            if self.visit[there_y][there_x]:
                continue
            s = self.board[there_y][there_x]
            if s not in here_node:
                continue
            self.visit[there_y][there_x] = True
            self.search(there_y, there_x, here_s + [s], here_node[s])
            self.visit[there_y][there_x] = False

    def getSentence(self):
        max_len, max_sentence = 0, ""
        temp = list(self.found)
        temp = sorted(temp, key=lambda x: (len, x))
        for sentence in temp:
            if max_len < len(sentence):
                max_len = len(sentence)
                max_sentence = sentence
        return max_sentence


def main():
    N = int(input())
    trie, words = Trie(), []
    for _ in range(N):
        trie.insert(input())
    input()  # 다음 공백 줄 제거용
    T = int(input())
    for t in range(T):
        trie.board = []
        trie.total = 0
        trie.find_sentence = ""
        trie.found = set()
        for i in range(4):
            trie.board.append(input())
        if t < T - 1:
            input()  # 다음 공백 줄 제거용
        for i in range(4):
            for j in range(4):
                s = trie.board[i][j]
                if s not in trie.root:
                    continue
                trie.visit[i][j] = True
                trie.search(i, j, [s], trie.root[s])
                trie.visit[i][j] = False
        print(trie.total, trie.getSentence(), len(trie.found))


if __name__ == "__main__":
    main()