백준 9202 Boggle (파이썬)

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

9202번: Boggle

풀이

이전에 풀었던 백준 전설19585 와 비슷한 문제이다. 이전 문제가 단순히 트라이를 사용하는 문제라면 해당 문제는 트라이와 DFS를 같이 조합해서 푸는 문제이다.

핑계처럼 들리겠지만 오랜만에 알고리즘 푸니까 쉽게 풀지는 못했다...

풀이법은 다음과 같다.

1. 문제에서 주어진 단어들로 트라이를 생성한다.

2. 주어지는 board를 기준으로 모든 칸마다 조건을 만족하면 DFS를 수행한다.

이때 조건은 여느 DFS와 동일하게 DFS를 수행할수 있는지 (board에 위치한 문자가 트라이의 시작 노드에 위치한다면 만족) 확인한다.

 

추가로 해당 문제는 pypy3로 해야 겨우 통과가 가능하다.

 

코드

import sys

input = lambda: sys.stdin.readline().rstrip()

dir = [[-1, 0], [-1, 1], [0, 1], [1, 1], [1, 0], [1, -1], [0, -1], [-1, -1]]
score = [0, 0, 0, 1, 1, 2, 3, 5, 11]


def makeTrie():
    tempDict = dict()
    numberOfWords = int(input())
    for _ in range(numberOfWords):
        word = input()
        now = tempDict
        for c in word:
            if not now.get(c):
                now[c] = dict()
            now = now[c]
        now[0] = 1

    return tempDict


def solve(x, y, now, word):
    if now.get(0):
        words.add(word)

    visit[x][y] = True
    for dir_x, dir_y in dir:
        x1 = x + dir_x
        y1 = y + dir_y
        if 0 <= x1 < 4 and 0 <= y1 < 4:
            if not visit[x1][y1]:
                c = board[x1][y1]
                if now.get(c):
                    solve(x1, y1, now.get(c), word + c)
    visit[x][y] = False


dictionary = makeTrie()
input()
numberOfBoard = int(input())
for _ in range(numberOfBoard):
    board = [list(input()) for _ in range(4)]
    visit = [[False] * 4 for _ in range(4)]
    words = set()
    for x in range(4):
        for y in range(4):
            c = board[x][y]
            if dictionary.get(c) and visit[x][y] == False:
                solve(x, y, dictionary.get(c), c)

    totalScore = sum([score[len(word)] for word in words])
    maxLength = sorted(list(words), key=lambda x: (-len(x), x))[0]
    totalWords = len(words)
    print(totalScore, maxLength, totalWords)
    input()