[Python] 보글 게임 (BOGGLE)

알고리즘 문제 해결 전략 - 06 무식하게 풀기 (Brute-Force 브루트 포스)

예제: 보글 게임 (문제 ID: BOGGLE, 난이도: 하)

보글(boggle)은 5X5 크기의 알파벳 격자를 가지고 하는 게임

게임의 목적은 상하좌우/대각선으로 인접한 칸들의 글자들을 이어서 단어를 찾아내는 것

각 글자들은 대각선으로도 이어질 수 있으며, 한 글자가 두 번 이상 사용될 수도 있음

 

문제 이해했고 C++로 구현되어 있는 코드를 파이썬으로 잘 변경했다

그대로 변경하지 않고 시작점을 주지 않고 모든 칸을 돌면서 찾는 방법으로 변경하였다

# 보글 게임판에서 단어를 찾는 재귀 호출 알고리즘

dx = [-1, -1, -1, 1, 1, 1, 0, 0]
dy = [-1, 0, 1, -1, 0, 1, -1, 1]


def hasWord(x, y, word, board):
    if 0 > x or x >= len(board) or 0 > y or y >= len(board[0]):
        return False
    elif board[x][y] != word[0]:
        return False
    elif len(word) == 1:
        return True
    for di in range(8):
        nx = x + dx[di]
        ny = y + dy[di]
        if hasWord(nx, ny, word[1:], board):
            return True
    return False


b = [['u', 'r', 'l', 'p', 'm'],
     ['x', 'p', 'r', 'e', 't'],
     ['g', 'i', 'a', 'e', 't'],
     ['x', 't', 'n', 'z', 'y'],
     ['x', 'o', 'q', 'r', 's']]


for i in range(5):
    for j in range(5):
        if hasWord(i, j, "pretty", b):
            print("찾았당")

 

근데 이제 여기서 찾은 글자를 출력하도록 좀 더 업그레이드를 시켜보고자 했다

# 보글 게임판에서 단어를 찾는 재귀 호출 알고리즘
import copy

dx = [-1, -1, -1, 1, 1, 1, 0, 0]
dy = [-1, 0, 1, -1, 0, 1, -1, 1]


def hasWord(x, y, word, board, mboard):
    myBoard = copy.deepcopy(mboard)
    if 0 > x or x >= len(board) or 0 > y or y >= len(board[0]):
        return False
    elif board[x][y] != word[0]:
        return False
    elif len(word) == 1:
        myBoard[x][y] = word[0]
        return myBoard
    for di in range(8):
        nx = x + dx[di]
        ny = y + dy[di]
        if k := hasWord(nx, ny, word[1:], board, myBoard):
            myBoard = k
            myBoard[x][y] = word[0]
            return myBoard
    return False


def draw(board):
    for i in range(len(board)):
        for j in range(len(board[i])):
            print(board[i][j], end=" ")
        print()


b = [['u', 'r', 'l', 'p', 'm'],
     ['x', 'p', 'r', 'e', 't'],
     ['g', 'i', 'a', 'e', 't'],
     ['x', 't', 'n', 'z', 'y'],
     ['x', 'o', 'q', 'r', 's']]

mb = [['*', '*', '*', '*', '*'],
      ['*', '*', '*', '*', '*'],
      ['*', '*', '*', '*', '*'],
      ['*', '*', '*', '*', '*'],
      ['*', '*', '*', '*', '*']]

for i in range(5):
    for j in range(5):
        if k := hasWord(i, j, "pretty", b, mb):
            draw(k)
            print("찾았당")

만족스럽게 풀었다!! 하고 끝내려다가

문득 여러개가 존재하는 et를 찾아보고자 했는데

결과는 참담하게도 두 개 밖에 나오지 않았다...

17행에서 for문이 하나를 찾아버리면 그대로 탈출해버리기 때문에 이런 대 참사가 일어난 것이다

문제를 찾았는데 슬프게도 해결 방법이 보이지 않는다

이걸 어떻게 해결할 것인가...

 

return이 아니라 리스트에 결과를 추가하는 식으로 모든 결과를 넣어주면 될 거 같긴 한데.... 일단 패스