브루트포스, 백트래킹

1. 브루트 포스(Brute-force)

문제를 해결하기 위해 가능한 모든 경우를 다 따지며 해를 찾는 간단하고 직관적인 알고리즘. 

모든 가능한 해를 찾아내는데 유용하지만, 문제의 크기가 커질수록 실행시간이 급격하게 증가하고 효율성이 낮아서 대부분은 다른 최적화 기법이나 다른 알고리즘을 사용한다. 보통 다음과 같은 과정으로 이루어진다. 

 

• 후보 생성 : 모든 가능한 후보 해를 생성한다. 
• 후보 평가 : 후보들을 평가하여 주어진 조건에 부합하는지 확인한다.
• 적합한 해 선택 : 문제의 요구조건에 따라 최적의 후보 해를 선택한다. 

 

예시) 백준 1182번 부분 수열의 합

 

문제
N개의 정수로 이루어진 수열이 있을 때, 크기가 양수인 부분수열 중에서 그 수열의 원소를 다 더한 값이 S가 되는 경우의 수를 구하는 프로그램을 작성하시오.

입력
첫째 줄에 정수의 개수를 나타내는 N과 정수 S가 주어진다. (1 ≤ N ≤ 20, |S| ≤ 1,000,000) 둘째 줄에 N개의 정수가 빈 칸을 사이에 두고 주어진다. 주어지는 정수의 절댓값은 100,000을 넘지 않는다.

출력
첫째 줄에 합이 S가 되는 부분수열의 개수를 출력한다.

 

예제 입력

5 0
-7 -3 -2 5 8

 

예제 출력

1

 

정답 코드

# n개의 수열이 주어졌을때 해당 수열의 부분 수열 중 총합이 S가 되는 경우의 수
# n개의 수의 부분 수열 중 더했을때 값이 s가 되는 경우의 수. => 조합 구하기.
# 1부터 n까지의 부분 수열을 구함. 그 중 총합이 s가 되는 경우만 결과 출력.

from itertools import combinations

n, s = map(int, input().split())
num = list(map(int, input().split()))
ls = [] # 1부터 n개까지의 부분 수열을 넣어줄 리스트

for i in range(1, n + 1): # 1부터 n개까지의 수의 조합을 구해 리스트에 추가
    ls.extend(list(combinations(num, i)))
    
cnt = 0 # 경우의 수

for i in ls: # 조합 리스트를 돌면서 조건 판단
    if sum(i) == s: # 총합이 s와 같다면 경우의 수 증가
        cnt += 1
        
print(cnt)

 

 

2. 백트래킹(Backtracking)

재귀적인 방식을 활용하여 해결책을 찾는 탐색 알고리즘. 현재 상태에서 가능한 모든 경로를 따라 들어가 탐색하다 원하는 값과 불일치하는 부분이 발생하면 더 이상 탐색을 진행하지 않고 전 단계로 돌아간다. 즉, 불필요한 탐색을 하지 않는다. 보통 트리 형태의 상태 공간을 탐색하는 데 사용된다. 조합, 순열 등 다양한 문제에 활용되지만 브루트 포스처럼 모든 가능한 조합을 탐색하는 특성상 입력 크기에 따라 시간 복잡도가 지수적으로 증가할 수 있다. 일반적으로 다음과 같은 과정으로 진행된다.

 

• 선택 : 문제의 조건에 따라 가능한 선택지 중 하나를 선택한다. 
• 조건 검사 : 선택한 것이 조건을 만족하는지 확인한다. 만족하지 않으면 다른 선택지를 시도한다. 
• 해결책 발견 / 백트래킹 : 선택한 것이 해결책이 되는지 확인하고, 그렇다면 알고리즘을 종료한다. 그렇지 않다면 백트래킹하여 이전 상태로 돌아간다.
• 재귀 호출 : 백트래킹을 통해 이전 상태로 되돌아왔다면 다른 선택지를 시도하기 위해 재귀 호출을 수행한다.
• 모든 경우 탐색 : 모든 가능한 선택지에 대해 위 과정을 해결책을 찾을때까지 반복한다. 

 

예시)  백준 10971 - 외판원 순회 2

문제
외판원 순회 문제는 영어로 Traveling Salesman problem (TSP) 라고 불리는 문제로 computer science 분야에서 가장 중요하게 취급되는 문제 중 하나이다. 여러 가지 변종 문제가 있으나, 여기서는 가장 일반적인 형태의 문제를 살펴보자.

1번부터 N번까지 번호가 매겨져 있는 도시들이 있고, 도시들 사이에는 길이 있다. (길이 없을 수도 있다) 이제 한 외판원이 어느 한 도시에서 출발해 N개의 도시를 모두 거쳐 다시 원래의 도시로 돌아오는 순회 여행 경로를 계획하려고 한다. 단, 한 번 갔던 도시로는 다시 갈 수 없다. (맨 마지막에 여행을 출발했던 도시로 돌아오는 것은 예외) 이런 여행 경로는 여러 가지가 있을 수 있는데, 가장 적은 비용을 들이는 여행 계획을 세우고자 한다.

각 도시간에 이동하는데 드는 비용은 행렬 W[i][j]형태로 주어진다. W[i][j]는 도시 i에서 도시 j로 가기 위한 비용을 나타낸다. 비용은 대칭적이지 않다. 즉, W[i][j] 는 W[j][i]와 다를 수 있다. 모든 도시간의 비용은 양의 정수이다. W[i][i]는 항상 0이다. 경우에 따라서 도시 i에서 도시 j로 갈 수 없는 경우도 있으며 이럴 경우 W[i][j]=0이라고 하자.

N과 비용 행렬이 주어졌을 때, 가장 적은 비용을 들이는 외판원의 순회 여행 경로를 구하는 프로그램을 작성하시오.

입력
첫째 줄에 도시의 수 N이 주어진다. (2 ≤ N ≤ 10) 다음 N개의 줄에는 비용 행렬이 주어진다. 각 행렬의 성분은 1,000,000 이하의 양의 정수이며, 갈 수 없는 경우는 0이 주어진다. W[i][j]는 도시 i에서 j로 가기 위한 비용을 나타낸다.

항상 순회할 수 있는 경우만 입력으로 주어진다.

출력
첫째 줄에 외판원의 순회에 필요한 최소 비용을 출력한다.

 

예제 입력 1

4
0 10 15 20
5 0 9 10
6 13 0 12
8 8 9 0

 

예제 출력 1

35

 

정답코드

# 요구사항 : 모든 도시 순회시 발생하는 최소 비용.
# 중복방문 안됨. 0,0은 제외. i, j가 0인 경우 갈 수 없는 곳임.
# 백트래킹. 모든 탐색을 진행하지만 불필요한 경우 이전단계로 돌아감.
import sys

def dfs(start, now, value, cnt): # 시작 도시, 현재 위치, 발생 비용, 방문한 도시 개수
    global ans # 전역 변수
    if cnt == N: # 만약 방문한 도시 개수가 주어진 것과 같다면 = 모든 도시를 방문했다면
        if a[now][start]: # 현재 위치에서 시작 위치로 돌아가는 비용이 있다면 = 시작위치로 돌아갈 수 있다면
            value += a[now][start] # 발생 비용에 추가
            if ans > value: # 만약 현재 발생 비용이 결과값보다 작다면
                ans = value # 최소값으로 결과값 갱신 후 종료
        return

    if value > ans: # 만약 현재 발생 비용이 결과값보다 크다면 => 최소 비용을 찾는 것임으로 더 진행할 필요 없음. 중지
        return

    for i in range(N): # 도시 개수만큼 반복
        if not visited[i] and a[now][i]: # 만약 방문하지 않은 곳이고, 현재 위치에서 갈 수 있는 곳이라면(=0이 아님)
            visited[i] = 1 # 방문 표시
            dfs(start, i, value + a[now][i], cnt + 1) # 해당 위치에서 갈수 있는 곳을 탐색하기 위해 함수 호출
            visited[i] = 0 # 함수 종료 후 다음 확인을 위해 방문 초기화

N = int(input()) # 도시 개수
a = [list(map(int, input().split()))for _ in range(N)] # 비용 행렬
ans = sys.maxsize # 정수 최댓값 가져오기
visited = [0] * N # 도시 방문 여부

for i in range(N): # 도시 개수만큼 반복
    visited[i] = 1 # 시작도시의 방문 여부 체크
    dfs(i, i, 0, 1) # dfs로 탐색
    visited[i] = 0 # 다음 탐색을 위해 방문여부 초기화

print(ans)