이전에 DFS문제를 풀며 백트래킹의 개념을 처음 접했던 기억이 있다. 나중에 한번 날잡고 제대로 공부해야지하고 미루고 미루다가 이번 포스팅을 통해 제대로 정리해보고자 한다.
백트래킹 기본 개념
기본적으로 백트래킹은 '가능한 모든 방법을 탐색한다'는데 기본 아이디어가 있다. 기본적으로 DFS는 현재 지점에서 방문할 곳이 있으면 재귀 호출을 이용해 모든 노드를 방문하는 완전 탐색 방법이다. 하지만 모든 곳을 방문하기 때문에 목표지점이 있지 않은 경로를 탐색할 수도 있다는 비효율성이 있다.
이를 개선할 수 있는 방식이 바로 백트래킹 알고리즘이다. 백트래킹은 DFS에 가지치기를 통해 갈 필요가 없는 루트를 고려하지 않고 탐색하는 기법이다. 본격적으로 문제와 코드를 통해 이해를 해보자
백트래킹 입문 문제 N과 M 시리즈
오늘 정복할 백트래킹 시리즈들...
먼저 첫번째 문제는 자연수 N과 M이 주어졌을때, 1부터 N까지의 자연수 중복에서 중복없이 M개를 고른 수열을 모두 구하라는 문제이다. 예를 들어, 
4,4 일경우 다음과 같은 수열들이 존재한다.
가장 먼저 든 생각은 어떻게 이 문제를 백트래킹의 관점에서 접근할 수 있을까!이다.
정말 단순히 m중 포문을 통해서도 원하는 조합을 가질수 있겠지만, 백트래킹을 사용하면 반복문을 중첩시킬 필요가 없어진다.
def dfs():
for i in range(1, n+1):
if visited[i]:
continue
visited[i] = True
s.append(i)
dfs()
s.pop()
visited[i] = False바로 이부분이 백트래킹을 사용한 핵심 알고리즘 코드이다.
visited 배열을 이용해 이미 방문 즉, 사용한 수이면 건너뛰게 만들어 중복되는 경우를 고려할 수 있게 만들었고, 중복되지 않는 경우에는 해당 값을 s 배열에 추가한다. 이후 dfs를 재귀호출하여 반복적으로 그 다음의 수를 탐색하며 들어간다.
이때
def dfs():
if len(s) == m:
print(' '.join(map(str, s)))
return
다음의 코드를 추가한다면, 정해진 배열의 길이에 도달했을때 해당 s 배열을 문제의 조건에 맞게 출력하고, return을 통해 함수 호출을 종료시킨다.
다시 원래의 코드를 돌아가 함수의 재귀적 호출이 끝나는 시점(길이가 m일때)에는, s배열에서 마지막 원소를 pop하고 해당 원소의 방문 여부를 초기화하여, 새로운 수를 탐색할 수 있도록 한다 .
위의 매커니즘을 살펴보면
처음에 재귀호출을 반복하여 1 2 3 4를 출력하고, 이후 길이가 4에 도달했기에 4를 pop하여 1 2 3 상태가 된다. 하지만, 이때 4는 여전히 방문처리가 된 상태이므로, 첫번째 if절에 걸리지 않고, 3을 한번더 pop하며, 이때 3번째 재귀의 for문의 i가 4가 되면 1 2 4 3 순으로 진행된다.
다음의 매커니즘을 반복하면
1 2 3 4 -> 1 2 4 3 -> 1 3 2 4 -> 1 3 4 2 ... 식으로
주어진 문제에 해당하는 답을 얻을 수 있다.
