Baekjoon: 9202 Boggle

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

풀이 과정
주어진 단어들을 음절마다 저장 ex. ICPC는 I, IC, ICP, ICPC 저장
4x4 보드를 순회하면서 음절이 있을경우 dfs(백트래킹)을 통해 해당 단어 등장 여부를 판별한다.

from collections import defaultdict, deque

n = int(input())
dx, dy = [0, 1, 1, 1, 0, -1, -1, -1], [1, 1, 0, -1, -1, -1, 0, 1]
words = set()
possible_set = set()

for _ in range(n):
    word = input()
    words.add(word)
    for z in range(len(word)):
        possible_set.add(word[:z + 1])

input()

b = int(input())
boards = []


for a in range(b):
    current_board = []
    for _ in range(4):
        current_board.append(input())
    boards.append(current_board)

    if a < b - 1:
        input()


def dfs(x, y, visited, now, now_board):
    global get_word
    if now in words:
        get_word.add(now)

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

        if not (0 <= nx < 4 and 0 <= ny < 4):
            continue

        if nx * 4 + ny in visited:
            continue

        if now + now_board[nx][ny] in possible_set:
            visited.add(nx * 4 + ny)
            dfs(nx, ny, visited, now + now_board[nx][ny], now_board)
            visited.remove(nx * 4 + ny)

    return


def func(grid):
    for i in range(4):
        for j in range(4):
            if grid[i][j] in possible_set:
                dfs(i, j, {i * 4 + j}, grid[i][j], grid)

    return


score = [-1, 0, 0, 1, 1, 2, 3, 5, 11]
for board in boards:
    get_word = set()
    func(board)
    total = 0
    max_length = 0
    max_word = 'z'
    for got in get_word:
        total += score[len(got)]
        if len(got) > max_length:
            max_length = len(got)
            max_word = got
        elif len(got) == max_length:
            max_word = min(max_word, got)

    print(total, max_word, len(get_word))