150415 보글 게임

보글게임에 대해 아는가?

보글게임은 게임판에서 문자가 랜덤하게 있고 그걸 이어서 문자열을 만드는 게임이다

예를 들어 

a l c d e

e o v e i

z z z z z

이런식으로 게임판이 되어있다면 (0,1), (1,1) (1, 2) (1, 3)을 이어서 love 라는 문자열을 만들 수 있다.

그렇다면 이 게임을 코드로 한번 짜보자

일단 완전탐색으로 구현한 보글게임이다.

# 미리 상대좌표 계산값을 리스트로 정의 dx = [-1, 0, 1, -1, 1, -1, 0, 1] dy = [-1, -1, -1, 0, 0, 1, 1, 1] def has_word(board, y, x, word): # 보드판 탐색에 제대로 들어가지 않는다면 False 반환 if len(board) <= y or len(board[0]) <= x or y < 0 or x < 0: return False # 첫번째 문자열이 맞지 않는다면 False if board[y][x] != word[0]: return False # 문자 길이가 1개면 True 반환 if len(word) is 1: return True # 상하좌우대각선을 완전탐색하여 다음 문자열이 있는지 확인한다. for i in xrange(8): if has_word(board, y + dy[i], x + dx[i], word[1:]): return True return False

일단 완전탐색으로 구현했기 때문에 느리다... 알고리즘 공부를 계속하면서 이 코드는 개선시켜 나가도록 하겠다.