[Algorithm] 백트래킹(backtracking)

백트래킹(backtracking)이란?

해를 찾는 도중 해가 아니어서 막히면, 되돌아가서 다시 해를 찾아가는 기법

백트래킹은 모든 가능한 경우의 수 중에서 특정한 조건을 만족하는 경우만 살펴보는 것이다.

어떤 문제를 푸는데 있어 모든 경우의 수를 시도하여 문제의 정답을 찾아나간다.

하지만 백트래킹에서는 한정조건에서의 모든 경우의 수를 시도하는 것이기 때문에 실제로 상당한 경우의 수들이 배제되기 때문에 단순 다중 for문 보다는 빠르게 해결되는 경우가 많다.

즉, 코딩에서는 반복문의 횟수까지 줄일 수 있으므로 효율적이다.

​

주로 문제 풀이에서는 DFS 등으로 모든 경우의 수를 탐색하는 과정에서, 조건문 등을 걸어 답이 절대로 될 수 없는 상황을 정의하고, 그러한 상황일 경우에는 탐색을 중지시킨 뒤 그 이전으로 돌아가서 다시 다른 경우를 탐색하게끔 구현한다.

---

백트래킹의 유망성 판단

어떤 노드의 유망성, 즉 해가 될 만한지 판단한 후에 유망하지 않다고 결정되면, 그 노드의 이전 노드 (부모)로 돌아가 (Backtracking) 다음 자식 노드로 이동한다.

해가 될 만한 가능성이 있으면 유망하다 (promising)고 하며, 유망하지 않은 노드에 가지 않는 것을 가지치기 (pruning)라고 한다.

---

백트래킹 구현

보통 백트래킹(BackTracking)의 구현은 BFS나 DFS와 함께 구현한다. 모든 경우의 수에서 한정

조건을 만족하는경우를 탐색하는 것이기 때문에 완전탐색기법인 BFS와 DFS가 모두 구현이 가능하다. 하지만 백트래킹의 특성에서 한정 조건에 부합하지 않다면(Node가 유망하지 않다면) 이전 수행(이전 Node)으로 돌아와야하기 때문에 BFS보다는 DFS의 구현이 더 편하다.

---

예시 코드

 

def dfs(cnt, idx): #현재까지 결과:cnt , 탐색 진행 인덱스:idx
    #r개를 선택한 경우
    if cnt == r: #백트래킹 예시
        return
    for i in range(idx,n): #재귀 호출 반복, n은 연결되어있는 노드
        if selected[i] == False: #탐색하지 않았을 때
            selected[i] = True   #상태변화
            dfs(cnt+1,i)         #재귀 호출
            selected[i] = False  #다음 경우의 수를 위해 상태 복구
        
selected = [] #탐색 유무 
r = 5 #node 개수

​

​

​