[Algorithm] 재귀와 완전 탐색

Posted on | In |

참고: 프로그래밍 대회에서 배우는 알고리즘 문제 해결 전략 (구종만 저)

http://grayt.tistory.com/16

이 글의 코드는 원저의 C++ 코드를 파이썬으로 옮긴 코드입니다.

컴퓨터의 강점은 처리 속도이기 때문에 작은 입력이 주어졌을 때 가능한 경우의 수를 모두 탐색하는 완전 탐색을 유용하게 사용할 수 있다. 이 때 재귀 호출을 이용하면 특정 조건을 만족하는 조합을 모두 생성하는 코드를 쉽게 작성할 수 있기 때문에 완전 탐색을 구현하는 데 유용하다.

예제: 중첩 반복문 대체하기

0번부터 차례대로 번호가 매겨진 n개의 원소 중 네 개를 고르는 모든 경우를 출력하는 코드를 작성해보자. 가장 간단한 풀이는 4중 for 문을 작성하는 것이다.

1
2
3
4
5
6
7
8
9
10
11
array = []
n = 7
for i in range(n):
    for j in range(i+1, n):
        for k in range(j+1, n):
            for l in range(k+1, n):
                array.append([i, j, k, l])

from pprint import pprint
pprint(array[:5])
# [[0, 1, 2, 3], [0, 1, 2, 4], [0, 1, 2, 5], [0, 1, 2, 6], [0, 1, 3, 4]]

하지만 골라야 하는 입력 개수가 늘어날 때마다 for 문을 늘려야하기 때문에 입력에 유연하게 대처할 수 없다. 이 때 재귀를 사용하면 입력에 유연하게 대처할 수 있다.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
def pick(n, picked, to_pick):
    """
    n: 전체 원소의 수
    picked: 지금까지 고른 원소들의 번호
    to_pick: 더 고를 원소의 수
    """
    # 기저 조건: 더 고를 원소가 없을 때 고른 원소들을 출력
    if to_pick == 0:
        print(picked)
        return
    
    if not picked:
        smallest = 0
    else:
        smallest = picked[-1] + 1
    
    for _next in range(smallest, n):
        picked.append(_next)
        pick(n, picked, to_pick-1)
        picked.pop(-1)
        
print(pick(7, [], 4))
>>>
[0, 1, 2, 3]
[0, 1, 2, 4]
[0, 1, 2, 5]
[0, 1, 2, 6]
...
[2, 4, 5, 6]
[3, 4, 5, 6]
None

예제: 보글 게임

보글은 5X5 크기의 알파벳 격자를 가지고 하는 게임이다. 게임의 목적은 상하, 좌우, 대각으로 인접한 칸들의 글자들을 이어 단어를 찾아내는 것이다. 한 글자가 두 번 이상 사용될 수도 있다. 주어진 칸에서 시작해 특정 단어를 찾을 수 있는지 확인하는 문제를 풀어본다. 함수는 다음과 같을 것이다. “$hasWord(y, x, word)$ = 보글 게임판의 (y, x)에서 시작하는 단어 word의 존재 여부를 리턴한다.”

간단한 방법은 완전 탐색을 이용해 단어를 찾아낼 때까지 인접한 모든 칸을 하나씩 시도해 보는 것이다. 그 중 한칸에서라도 단어를 찾을 수 있으면 성공이고 어느 칸을 선택하더라도 답을 찾을 수 없다면 실패가 된다.

문제의 분할

$hasWord()$ 가 하는 일을 가장 자연스럽게 조각내는 방법은 각 글자를 하나의 조각으로 만드는 것이다. 먼저 시작 위치의 글자가 단어의 첫 글자와 일치하면 원래 단어에서 첫 글자를 뗀 word[1:]을 격자에서 다시 찾는다. 인접한 여덟 경우를 모두 탐색한다.

기저 사례의 선택

더 이상의 탐색 없이 간단히 답을 낼 수 있는 다음 경우들으 기저 사례로 선택한다.

  • 위치 (y, x)에 있는 글자가 원하는 단어의 첫 글자가 아닌 경우 항상 실패
  • (1번이 아닌 경우) 원하는 단어가 한 글자인 경우 항상 성공

단, 위의 두 조건의 순서는 바뀌면 안 된다.

  • 또한 입력값이 격자의 범위를 벗어난 경우도 기저 사례로 선택해 가장 먼저 처리한다.

구현

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
dx = np.array([-1, -1, -1, 1, 1, 1, 0, 0])
dy = np.array([-1, 1, 0, -1, 0, 1, -1, 1])

def has_word(y, x, word):
    # 기저 1: board의 범위를 벗어나는 경우
    if (y > len(board)) and (x > len(board[0])):
        return False
    # 기저 2: 첫 글자가 좌표의 위치의 글자와 다를 경우
    if board[y][x] != word[0]:
        return False
    # 기저 3: 글자가 1개면 더 이상 비교할 게 남아 있지 않음
    if len(word) == 1:
        return True
    for direction in range(8):
        next_y = y + dy[direction]
        next_x = x + dx[direction]        
        # 여기까지 왔다는 것은 이미 첫 글자가 일치한 경우이므로
        # 그 다음 글자부터 다시 시작
        # 한 방향으로 무식하게 파고 들어가는 완전 탐색
        if has_word(next_y, next_x, word[1:]):
            return True
    return False

실행 결과는 다음과 같다.

1
2
3
4
5
6
7
8
board = np.array([['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']])

print(has_word(2, 0, 'GIRL'))
# True