[알고리즘] 배열에서 글자 찾아내기

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

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

# 한글자만 검사하는 방식으로 기저사례를 찾아내었다.
def hasWord(y, x, word, a):
	# 기저사례1 : 범위 넘어가지 않기
    if (x < 0 or x >= len(a) or y < 0 or y >= len(a)):return False
    # 기저사례2 : 첫글자가 다를 경우
    if (a[y][x] != word[0]): return False
    # 위 거름망 통과 후에 길이가 1이라면 첫글자도 같고, 범위도 넘어가지 않는 경우이므로
    # 참 반환
    if (len(word) == 1): return True
    for dir in range(len(dx)):
        nextY = y + dy[dir]
        nextX = x + dx[dir]
        # if문 재귀함수 호출로, word[1:]으로 substr 해주어 word[0]처럼 한글자씩 뽑을 수 있게한다.
        if (hasWord(nextY, nextX, word[1:],a)): return True
    return False


a = [['n', 'n', 'n', 'n', 's'],
     ['n', 'e', 'e', 'e', 'n'],
     ['n', 'e', 'y', 'e', 'n'],
     ['n', 'e', 'e', 'e', 'n'],
     ['n', 'n', 'n', 'n', 'n'],]

if(hasWord(2,2,'yes',a)):
    print("성공입니다")
else:
    print("그런 글자는 없습니다.")