06. 완전탐색 (Brute Force)

완전 탐색(Brute Force)

무식하게 풀기
"컴퓨터의 빠른 계산능력을 이용해 가능한 경우의 수를 일일이 나열하면서 답을 찾는 방법" 즉, 가능한 방법을 전부 만들어 보는 알고리즘

재귀함수 호출과 for반복문

반복의 깊이가 비교적 얕고 그 수가 정해져있을 때는 for문으로 구현하는 것이 간단하나 깊이가 정해져있지 않고 깊을때는 재귀함수 호출을 이용해서 완전탐색을 시도할 수 있다.

여기서는 전반적으로 재귀함수 호출 방식을 사용하였다.

1) 재귀함수

• 자신이 수행할 작업을 유사한 형태의 여러 조각으로 쪼갠 뒤 그 중 한 조각을 수행하고, 나머지를 자기 자신을 호출해 시행하는 함수
• 모든 재귀함수는 기저사례(base case)를 포함해야한다. <- 더이상 쪼개지지 않는 가장 작은 작업

◈ 예제1

# 1부터 n까지 합을 계산하는 함수
def recursiveSum(n):
    if n == 1:
        return 1;
    return n + resursiveSum(n-1);

◈ 예제2

# 0부터 n-1까지 총 n개의 수 중에서 4개를 고르는 모든 경우를 출력
def pick(n, picked, toPick):
    if toPick == 0:
        print(''.join(map(str, picked)))
        return
    
    smallest = 0
    if picked:
        smallest = picked[-1] + 1
    for next in range(smallest, n):
        picked.append(next)
        pick(n, picked, toPick - 1)
        picked.pop()

pick(5, [], 4)

◈ 예제3

상하좌우/대각선으로 인접한 칸들의 글자들을 이어서 단어를 찾아내는 것
hasWord(y, x, word) = 보글 게임판의 (y, x)에서 시작하는 단어 word의 존재 여부 반환

# 보글게임

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

board = [
    ['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(y, x, word):
    if y < 0 or y >= len(board) or x < 0 or x >= len(board): 
        return False
    
    if board[y][x] != word[0]:
        return False
    
    if len(word) == 1:
        return True
    
    for dir in range(8):
        nextY = y + dy[dir]
        nextX = x + dx[dir]
        
        if hasWord(nextY, nextX, word[1:]):
            return True
    return False

print(hasWord(1, 1, "PITO"))  //True

완전 탐색 레시피

1. 완전 탐색은 존재하는 모든 답을 하나씩 검사하므로, 걸리는 시간은 가능한 답의 수에 정확히 비례한다. 이를 이용해, 최대 크기의 비력을 가정했을 때 답의 개수를 계산하고 이들을 모두 제한 시간안에 생성할 수 있을지 가늠한다.
2. 가능한 모든 답의 후보를 만드는 과정을 여러 개의 선택으로 나눈다. 각 선택은 답의 후보를 만드는 과정의 한 조각이 된다.
3. 그 중 하나의 조각을 선택해 답의 일부를 만들고, 나머지 답을 재귀 호출을 통해 완성한다.
4. 조각이 하나 밖에 남지 않은 경우, 혹은 하나라도 남지 않은 경우에는 답을 생성했으므로 이것을 기저 사례로 선택해 처리한다.

◈ 예제4: 소풍

각 학생들의 쌍에 대해 이들이 서로 친구인지 여부가 주어질때, 학생들을 짝지어 줄 수 있는 방법의 수를 계산하는 프로그램

n, m = 4, 6
a = [0, 1, 1, 2, 2, 3, 3, 0, 0, 2, 1, 3]
s = [i for i in range(n)]
areFriends = [[False] * n for _ in range(n)]
for i in range(0, 2*m-1, 2):
    areFriends[a[i]][a[i+1]] = True
    areFriends[a[i+1]][a[i]] = True

for row in areFriends:
    print(' '.join(map(str,row)))
check = [False] * n
# 무조건 2명씩 짝지어주면됨


def soulmate(check):
    firstFree = -1
    for i in range(n):
        if not check[i]:
            firstFree = i
            break
    if firstFree == -1:
        return 1
    ret = 0
    for pairwith in range(firstFree+1, n):
        if not check[pairwith] and areFriends[firstFree][pairwith]:
            check[pairwith] = check[firstFree] = True
            ret += soulmate(check)
            check[pairwith] = check[firstFree] = False
    return ret

print(soulmate(check))

◈ 예제4: TSP문제

한 영업사원이 한 도시에서 출발해 다른 도시들을 전부 한 번씩 방문한 뒤 시작도시로 돌아온다. 도시들이 모두 연결되어있다고 할때, 가능한 모든 경로 중 가장 짧은 경로를 찾아라.

• 모든 도시를 다 방문했을 때 기저사례 조건을 생성하고 함수를 종료시킨다.

n = 3
a = [i for i in range(n)]
d = [
    [0, 2, 3],
    [2, 0, 6], 
    [3, 6, 0]
]
visited = [False] * n

def tsp(path, visited, cur):

    if len(visited) == n:
        if path:
            return cur + d[path[0]][path[-1]]

    ret = 98765432100
    for i in range(n):
        if visited[i]:
            continue
        path.append(i)
        visited[i] = True
        if path:
            here = path[-1]
            cand = tsp(path, visited, cur + d[here][i])
            ret = min(ret, cand)
        visited[i] = False
        path.pop()
    return ret


print(tsp([], visited, 0))

결론

완전탐색은 재귀호출이나 for/while 반복문을 사용하여 단순하게 혹은 무식하게 모든 경우의 수를 다 조합해보는 방법이다. 문제에 주어진 입력의 최대값을 이용해서 시간복잡도를 먼저 짐작해보고 10억(컴퓨터 계산 1초)보다 작은 경우에만 완전탐색으로 하는게 의미가 있다고 할 수 있다. 선택하는 것의 갯수가 정해져있는 경우는 for문을, case마다 다른 경우는 재귀함수 로 구현하는 것이 일반적이다. (재귀함수 연습을 많이 해야겠다.)