보글 게임

 

algospot.com :: BOGGLE

 

GitHub - Seungkyu-Han/PS_strategy: 알고리즘 분류하는 워크플레이스

이 보글게임 문제를 브루트포스, 재귀로 풀 수 있다. (그냥 알고리즘만 구현해보고 채점은 안해봐서 모르겠다... 그냥  참고만)

def hasword(cur_x, cur_y, target_word, visited):  # 해당 위치에 찾는 단어가 있는지 확인하는 함수
    # 범위를 확인하지 않고 넘어오기 때문에 범위 확인을 가장 먼저 해준다.
    if not (0 <= cur_x < 5 and 0 <= cur_y < 5):
        return False

    if len(target_word) == 0:
        return True

    if target_word[0] != board[cur_x][cur_y]:
        return False

    for t in range(8):
        go_x = cur_x + dx[t]
        go_y = cur_y + dy[t]

        if not (0 <= go_x < 5 and 0 <= go_y < 5):
            continue

        if not visited[go_x][go_y]:
            continue

        visited[go_x][go_y] = False
        if hasword(go_x, go_y, target_word[1:], visited):
            return True
        visited[go_x][go_y] = True

    return False

이 알고리즘에서 가장 중요한 함수이다.

이 문제를 해결하기 위해서는

현재 위치(cur_x, cur_y)에 첫 글자가 있는가?

주위의 8칸 중, 그 위치에서 시작해서 단어의 나머지 글자들을 찾을 수 있는가? 를 알아야 한다.

여기서 현재 위치에 첫 글자가 있으면, 주위 칸으로 가서 두번째 문자부터 시작하면 된다.

이 일을 문자가 없어질 때까지 반복한다. (target_len의 길이 == 0이 종료조건)

이렇게 문제를 부분 문제로 나누어서 풀 수 있어야 한다. (솔직히 떠올리기가 어려운 것 같다.)

 

이 알고리즘을 구현하면서 visited를 사용해 한 글자를 두 번 이상 사용하지 못하게 만들었다.

N = int(input('단어의 수를 입력 : '))

words = []

for i in range(N):
    words.append(list(input().strip()))

print('보드를 입력')

board = []

for i in range(5):
    board.append(list(input().strip()))

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


def hasword(cur_x, cur_y, target_word, visited):  # 해당 위치에 찾는 단어가 있는지 확인하는 함수
    # 범위를 확인하지 않고 넘어오기 때문에 범위 확인을 가장 먼저 해준다.
    if not (0 <= cur_x < 5 and 0 <= cur_y < 5):
        return False

    if len(target_word) == 0:
        return True

    if target_word[0] != board[cur_x][cur_y]:
        return False

    for t in range(8):
        go_x = cur_x + dx[t]
        go_y = cur_y + dy[t]

        if not (0 <= go_x < 5 and 0 <= go_y < 5):
            continue

        if not visited[go_x][go_y]:
            continue

        visited[go_x][go_y] = False
        if hasword(go_x, go_y, target_word[1:], visited):
            return True
        visited[go_x][go_y] = True

    return False


def solve(target_word):
    for q in range(5):
        for w in range(5):
            visited_list = [[True] * 5 for i in range(5)]
            if hasword(q, w, target_word, visited_list):
                return True
    return False


for i in range(N):
    if solve(words[i]):
        print(*words[i])

위 함수를 포함한 전체 코드이다.

단어가 많아진다면 트라이를 통해서 더 빠르게 구현할 수 있겠지만 난이도는 많이 높아질 것 같다....