[BOJ/백준] 9202 Boggle 파이썬

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

9202번: Boggle

 

트라이와 DFS를 사용해서 풀었다.

 

단어 사전에 단어가 최대 30만개 이므로 검색 시 오래 걸릴 것이다.

그래서 트라이로 단어 사전을 재구성하자.

트라이의 노드는 현재 글자, 자식, 단어의 끝 상태 3가지로 구성했다.

단어의 끝은 해당 글자로 끝나는 단어가 있다면 True로 설정했다.

 

그리고 boggle의 모든점에서 DFS를 실행하자.

이때 트라이도 함께 가져가자.

각 글자를 트라이에서 찾아서 해당 노드를 가지고 DFS를 진행하자.

예를 들어 

트라이에 A-B-C-D로 된 단어가 들어있고

boggle이

AAAA

BBBB

CCCC

DDDD

라고 해보자

처음에는 0,0에서 시작한다.

우선 0,0의 글자가 트라이의 헤드에 있는지 검사하고 있다면 해당 좌표에서 DFS를 실행하고 없다면 다음 좌표로 넘어가자.

 

트라이 헤드에 A가 있으므로 DFS를 실행하는데 이때 헤드의 A 자식 노드를 가지고 가자.

0,0에서 상하좌우대각선을 모두 확인하면서 해당 글자가 현재 노드의 자식 노드에 있는지 확인하자.

만약 있다면 해당방향으로 진행하자.

이런식으로 최대 단어가 8자가 될때까지 진행하자.

이때 방문한 점은 다시 방문하면 안된다. 이점을 체크하지 않아 틀렸었다.

 

 

그리고 DFS를 실행할 때마다 현재 노드의 is_end flag가 True인지 확인하자.

is_end flag는 단어의 끝을 표시한 것이므로 True라면 단어 사전의 단어가 완성됐다는 것이다.

따라서 해당 단어를 저장하자. 중복을 제거해야하므로 set 자료구조를 활용 했다.

 

from sys import stdin

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

w = int(input())
word_dictionary = []
for _ in range(w):
    word_dictionary.append(input().strip())
input()

def solv():
    tri = make_tri()

    b = int(input())
    for _ in range(b):
        board = [list(input().strip()) for _ in range(4)]
        search_result = set()
        visited = [[False]*4 for _ in range(4)]
        for x in range(4):
            for y in range(4):
                now = tri
                for child in now.child:
                    if board[x][y] == child.alpha:
                        if child.is_end:
                            search_result.add(board[x][y])
                        visited[x][y] = True
                        search_word(child,x,y,board,board[x][y],search_result,visited)
                        visited[x][y] = False
                        break
        input()
        score = 0
        long_word = ''
        words = sorted(search_result)
        for word in words:
            if len(long_word) < len(word):
                long_word = word
            score += calc_score(word)
        print(score, long_word, len(words))
class Node(object):
    def __init__(self,alpha=''):
        self.alpha = alpha
        self.child = []
        self.is_end = False
def make_tri():
    tri = Node()

    for word in word_dictionary:
        now = tri
        for alpha in word:
            flag = False
            for child in now.child:
                if child.alpha == alpha:
                    now = child
                    flag = True
                    break
            if not flag:
                child = Node(alpha)
                now.child.append(child)
                now = child
        now.is_end = True
    return tri

def search_word(now,x,y,board,word,search_result,visited):
    if now.is_end:
        search_result.add(word)

    if len(word) == 8:
        return

    for d in range(8):
        nx = x + dx[d]
        ny = y + dy[d]

        if point_validator(nx,ny,visited):
            alpha = board[nx][ny]
            for child in now.child:
                if child.alpha == alpha:
                    visited[nx][ny] = True
                    search_word(child,nx,ny,board,word+board[nx][ny],search_result,visited)
                    visited[nx][ny] = False
def point_validator(x,y,visited):
    if x < 0 or y < 0 or x >= 4 or y >= 4:
        return False
    elif visited[x][y]:
        return False
    return True

def calc_score(word):
    word_lenght = len(word)
    if word_lenght == 8:
        return 11
    elif word_lenght == 7:
        return 5
    elif word_lenght == 6:
        return 3
    elif word_lenght == 5:
        return 2
    elif word_lenght in [3,4]:
        return 1
    else:
        return 0
solv()