[Python] 재귀호출 - 보글 게임 ( Boggle Game )

 

 

완전 탐색에는 두 가지 방법이 있다. 

 

1. 반복문

2. 재귀 호출

 

 

반복문은 모든 데이터에 접근할 때 사용되고 재귀호출은 모든 데이터 '조합'에 접근할 때 사용한다. 

 

 

보글 게임 ( Boggle Game )

5x5  알파벳 보드판에 상하좌우 및 대각선으로 인접한 칸들을 이동하면서 찾고자 하는 '단어'를 찾는 게임이다.

 

 

단어 'PRETTY'를 찾는다고 가정하자.

 

'PRETTY'는 하나의 알파벳이 아닌 알파벳의 '조합'이다. 단순히 알파벳 P를 찾는 문제이면 이중 for문(반복문)을 이용하여 완전탐색하면 된다. 하지만 BOGGLE 게임은 알파벳 '조합'을 찾는 문제이다. 

 

 

1. 데이터 

- 상하좌우/대각선 이동 데이터 ( 자료구조 : 배열 )

- 보글게임 보드판 ( 자료구조 : 배열 )

 

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

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']]

 

2. 알고리즘

2-1) 보드판의 알파벳을 하나씩 완전탐색하며 단어 첫 시작인 'p'를 찾아야 한다. ( 반복문 : 2중 for문 )

2-2) 원하는 단어를 찾으면 다음 단어를 찾기 위해 상하좌우/대각선 모든 경우를 하나씩 완전탐색한다. ( 반복문 )

2-3) 이동한 좌표의 단어가 조건에 부합하는지 여부를 판단하고 부합하다면 함수를 재귀호출하여 단어조합 시퀀스를 유지한다. ( 단어 조합 : 재귀호출 )

 

3. 조건

- 상하좌우/대각선 인접한 칸에 PRETTY 순서의 단어 조합을 찾아야 한다. 

-  x,y는 5x5를 벗어나면 안 된다. 

 

4. 코드 

# 데이터 영역
# 1) 상하좌우/대각선 이동 데이터
dx = [-1,-1,-1,1,1,1,0,0]
dy = [-1,0,1,-1,0,1,-1,1]

# 2) Boggle 보드판 데이터
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']]

# 알고리즘 영역
def hasWord(x,y,word,board):
    
    # 조건 영역
    # 1) 좌표는 Boggle 판을 넘어서면 안 된다. 
    if x < 0 or x >= len(board) or y < 0 or y >= len(board[0]):
        return False
    # 2) 좌표의 단어가 부합하지 않으면 재귀호출 시퀀스를 종료시킨다.
    elif board[x][y] != word[0] :
        return False
    # 3) 1),2) 조건을 통과하고 이번 재귀호출이 마지막 단어탐색이라면 True를 반환하여 재귀호출 시퀀스를 종료시킨다. 
    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): # True를 Return하면 True를 반환하여 재귀호출 시퀀스를 종료시킨다. 
            return True
        
    return False # for문을 모두 돌았는데도 True가 반환되지 못하면 False를 반환하여 재귀호출 시퀀스를 종료시킨다.

# Boggle 보드판 첫 이동 : 완전탐색 ( 반복문 )
for i in range(5):
    for j in range(5):
        if hasWord(i,j,"pretty",b): # 재귀호출의 시퀀스의 Return이 True이면 pretty 단어 탐색 성공, COMPLETE 출력!
            print("COMPLETE")

 

 

 

---

 

 

참고자료 

알고리즘 문제 해결 전략 세트 - YES24