백트래킹 개념을 잡자

 

백트래킹은 주로 재귀를 이용한 브루트포스 문제풀이에 쓰이는 알고리즘입니다. 특정 조건이 주어졌을 때 가능한 모든 해의 경우를 셀 때 등에 유용합니다. 백트래킹은 백날 개념을 설명해봐야 코드보고 이해하는 것만 못합니다. 가장 대표적인 N과 M 시리즈를 봅시다.

 

 

# N과 M 시리즈

https://www.acmicpc.net/problem/15649

15649번: N과 M (1)

백트래킹의 가장 대표적인 문제 유형인 N과 M입니다. 고등학교 수학에서 nCm이라 불리는 조합을 찾아내는 문제인데요, 사실 파이썬 itertools 라이브러리의 combinations를 쓰면 내장 함수만으로도 문제를 쉽게 푸는게 가능하지만, 백트래킹 알고리즘을 겨냥하고 출제된 문제는 itertools만으론 해결 안되는 경우가 많기 때문에 어떻게 재귀함수와 그 조건을 설정할 것인지 알아야 합니다.

 

 

백트래킹은 정답을 보고 이해하는게 빠릅니다. 주어진 n에 대해, 1부터 n까지 중복 없이 m개의 수를 선택하여 출력하는 문제입니다.

n,m = map(int,input().split())
candidate = [i for i in range(1,n+1)]

def search(cur):
    if len(cur)==m:
        print(*cur)
        return
    for i in candidate:
        if i not in cur:
            search(cur + [i])

search([])

candidate에는 선택할 숫자의 목록이 담겨있습니다. n이 3이라면 candidate는 [1, 2, 3]이 될 것이고, n이 6이라면 [1, 2, 3, 4, 5, 6]이 될 것입니다.

 

search()는 실제로 가능한 해를 재귀적으로 탐색하는 함수입니다. 파라미터 값인 cur에는 현재 선택된 수의 목록이 들어있습니다. 만약 선택된 수의 개수가 m개, 즉 문제에서 요구하는 갯수와 같다면 답으로 print하고 return하여 탐색을 끝냅니다. 그렇지 않다면, candidate를 돌며 현재 선택되지 않는 수를 한 개 추가해서 search를 재귀적으로 호출합니다.

 

search([])를 호출해서, 최초에 빈 cur을 함수의 인자로 주고 탐색을 시작하도록 합니다. search()는 cur에 아직 존재하지 않는 candidate의 요소들을 m개가 될때까지 탐색하며, m개가 될 때 비로소 출력하고 로직을 마무리할 것입니다.

 

어렵지 않죠? M과 N시리즈는 대체적으로 이런 느낌입니다. 위는 단순한 조합 문제이지만 조합이 아닌 순열, 중복 순열, 중복 조합 등으로 응용된 것이 나머지 시리즈입니다. 그럴땐 조건을 위처럼 `for i not in cur`로 주지 않고 단순하게 추가하거나 idx를 고려사항에 넣지 않는 식으로 구현할 수 있습니다.

 

 

이제 백트래킹을 이용해서 풀 수 있는 문제 몇 가지를 풀어보겠습니다.

 

 

 

# 백준 1038 : 감소하는 수

아주아주 대표적인 백트래킹 문제입니다. 자릿수가 커질 때마다 감소하는 숫자를 "감소하는 수"라고 했을 때, N번째 감소하는 수를 묻고 있습니다. 감소하는 수의 크기는 사실 정해져 있습니다. "9876543210"이 마지막 감소하는 수겠죠. 따라서 실제로 N번째의 감소하는 수를 구하는 대신(그렇게 콕 집어서 구하는 알고리즘을 구현하는 것 역시 쉽지않다) 감소하는 수 전부를 구해서 그 중 N번째 숫자를 뽑는 것으로 문제를 풀겠습니다.

n = int(input())
ans = []

num = ['9','8','7','6','5','4','3','2','1','0']
def search(cur,idx):
    global ans
    if cur!='':
        ans.append(int(cur))

    for i in range(idx,len(num)):
        search(cur+num[i],i+1)

search('',0)
ans.sort()
if (n>=len(ans)):
    print(-1)
else:
    print(ans[n])

ans는 감소하는 수가 들어있는 결과 리스트입니다. search는 실제로 백트래킹을 실행하는 함수인데, 인자로 "현재 감소하는 수"인 cur 문자열, 그리고 현재 탐색중인 인덱스인 idx를 가집니다. num 리스트를 보면 알겠지만 한자리 자연수에 대해 내림차순으로 정렬되어있는데, cur 뒤에 붙을 수 있는 숫자들은 num 리스트에서 idx 이상의 인덱스를 가진 숫자들만 가능함을 표현하기 위함입니다.

 

for i in range(idx,len(num))을 봅시다. 현재 감소하는 수인 cur 문자열에 num[i]를 추가하고 있습니다. "cur 뒤에 붙을 수 있는 숫자들은 num 리스트에서 idx 이상의 인덱스를 가진 숫자들만 가능"이라고 했기 때문에 idx부터 시작하는 겁니다. num[i]가 cur의 끝에 추가되었기 때문에 i 이하의 인덱스를 가진(즉 뒤에 붙었을 때 감소하는 수열이 만들어지지 않는) num 리스트의 요소들은 더이상 cur+num[i]뒤에 붙을 수 없습니다. 해당 조건을 추가하기 위해 다음 search를 호출할 때 idx 값으로 i+1을 주는 것입니다.

 

작은 순서대로 정렬하기 위해 ans.sort()를 호출했습니다. 또한 N번째 감소하는 수가 없을 경우 -1을 출력하라 했으므로, n 범위를 검사하는 것으로 마무리하면 되겠습니다.

 

 

# 백준 1182 : 부분수열의 합

조금은 어렵게 느껴질 수도 있는 문제입니다. 연속할 필요가 없는 부분수열의 합이 s가 되는 경우의 수를 구하는 문제입니다. 주어진 리스트에서 1개 이상의 요소를 뽑았을 때 그 합이 s와 같은 경우의 수를 구해야 합니다. 이것것도 역시 itertools.combitantions로 i=1부터 N까지 nCi를 하는 방법으로 풀 수도 있지만 재귀+브루트포스를 사용해봅시다.

n,s = map(int,input().split())
ans = 0
numbers = list(map(int,input().split()))

def search(cur,idx):
    global ans
    if cur==s:
        ans += 1
    for i in range(idx,n):
        search(cur+numbers[i],i+1)

search(0,0)
if s==0:
    ans -= 1
print(ans)

cur은 현재 고려중인 부분수열의 총합, idx는 이 다음에 고려해야하는 수열의 인덱스입니다. cur이 문제 조건과 같을 때 정답에 1을 더하는 것은 쉽게 이해할 수 있을 것입니다.

 

s가 0이었을 때 답에서 1을 빼는 이유는, 문제 조건이 길이가 양수인 부분수열이기 때문입니다. 아무것도 없는 최초의 조건, 즉 search(0,0)은 합은 0이면서 길이가 0인 부분수열이 됩니다. 이는 조건을 만족하지 않기 때문에 정답에서 제외해야합니다. 

 

 

# 백준 1062 : 가르침

이번엔 아예 itertools 라이브러리를 사용해서 문제를 풀어보겠습니다. k개의 알파벳을 읽을 수 있다고 할 때, 주어진 단어를 가장 많이 읽을 수 있는 경우 그 개수를 출력하는 문제입니다.

 

일단 문제에서 "ancti" 5개 알파벳은 모든 단어에 들어가있다고 했으므로 k가 5 미만인 경우에는 가차없이 0을 출력하고 끝냅니다. 그리고 일단 "ancti"는 무조건 가르쳐야 하는 단어로 추가합니다. 동시에 k-=5를 하여 실질적으로 새로 배울 수 있는 글자는 k-5개임을 나타냅니다.

 

그 뒤, "ancti"와 그를 제외한 알파벳 k-5개를 뽑아 "읽을 수 있는" 문자를 저장한 리스트에 담아두고, 문제에서 주어진 단어들을 돌며 읽을 수 있는 개수를 알아냅니다. max 함수를 통해 최적해를 찾으면 됩니다. 밑줄친 알파벳 5개를 뽑는 작업이 백트래킹을 이용한 조합이 되는데, 이를 itertools.combinations를 이용해서 풀어보면 아래와 같습니다.

from itertools import combinations

n,k = map(int,input().split())

words = []
for _ in range(n):
    words.append(input().rstrip())
if k<5:
    print(0)
    exit()
k -= 5

ans = 0
alph = list('bdefghjklmopqrsuvwxyz')
for c in combinations(alph,k):
    can = 0
    know = ['a','n','c','t','i'] + list(c)
    for word in words:
        read = True
        for s in word:
            if s not in know:
                read = False
                break
        if (read):
            can += 1
    ans = max(ans,can)
print(ans)

만약 itertools를 사용하지 않는다면 k-5개의 문자를 구성하는 search() 백트래킹 함수를 만들어놓고 문자가 구성되었을 때 몇 개의 단어를 읽을 수 있는지 체크한 뒤 답을 업데이트 하는 전략을 취할 것 같네요.

 

 

 

# 백준 2023 : 신기한 소수

소수(prime number)가 결합된 백트래킹 문제입니다. N자리의 수가 있을 때, 앞에서부터 1, 2, 3, ..., N자리까지 자른 수가 모두 소수인 수를 출력하는 것입니다.

 

일단 isPrime(n)을 정의해서 인자로 들어온 n이 소수인지를 판별하는 함수를 만듭니다(이 로직은 기본적인 내용으로 생략하겠습니다).

백트래킹 로직을 수행하는 search()함수는 인자로 현재 탐색중인 "신기한 소수" cur 뒤에 숫자를 추가해가며 추가한 수가 소수가 될 수 있는지 여부를 판별하며 자릿수를 늘려가는 행위를 반복합니다. 만약 cur이 문제에서 제시하는 수의 길이인 n과 같다면 print()를 하는 것이죠.

n = int(input())

def search(cur):
    if len(str(cur))==n:
        print(cur)
        return
    
    for i in range(10):
        candidate = int(str(cur)+str(i))
        if isPrime(candidate):
            search(candidate)

def isPrime(n):
    if n==1:
        return False
    if n==2:
        return True
    for i in range(2,int(n**0.5)+1):
        if (n%i==0):
            return False
    return True

for i in range(2,10):
    if isPrime(i):
        search(i)

작은 수부터 출력하라고 했지만, search는 최초에 호출할 때부터 다음 자릿수를 탐색할 때까지 작은 숫자부터 탐색을 진행하므로 결과를 출력할 때 따로 정렬을 해주지 않아도 됩니다.

 

 

 

 

# 백준 1189 : 컴백홈

깊이가 정해진 DFS를 수행할 때 목적지에 갈 수 있는지 여부를 체킹하여 그 경우의 수를 구하는 문제입니다. depth(=k)를 기준으로 구현해야 하니 DFS와 백트래킹을 이용해서 k만큼의 거리를 지나왔을 때 목표하는 도착점과 같은지 체크하고 같다면 경우의 수를 1 더하는 식으로 구현하면 끝인 어렵지 않은 문제입니다만... 그냥 DFS문제가 아닌지?  (사실 백트래킹 완탐이 visited를 기준으로 다음 노드를 탐색하는 DFS랑 크게 다를게 없긴 합니다)

r,c,k = map(int,input().split())
graph = []
for _ in range(r):
    graph.append(list(input().strip()))

ans = 0
def search(x,y,visited):
    global ans
    if len(count)==k:
        if x==0 and y==c-1:
            ans += 1
        return
    
    dx,dy = [-1,1,0,0],[0,0,-1,1]
    for i in range(4):
        nx,ny = x+dx[i],y+dy[i]
        if (0<=nx<r and 0<=ny<c and graph[nx][ny]!="T" and (nx,ny) not in visited):
            search(nx,ny,count+1,visited+[(nx,ny)])

search(r-1,0,[(r-1,0)])
print(ans)

 

 

 

백트래킹이라는 멋있어 보이는 알고리즘 이름이 있지만, 사실은 간지나게 재귀하기(?)로 불러도 되지 않을까 싶고요.