백트래킹(Backtracking) 이란?

백트래킹이란?

재귀적으로 문제를 하나씩 풀어가되, 현재 재귀를 통해 확인 중인 상태(노드)가 제한 조건에 위배되는지 (유망[promising]하지 않은지) 판단하고 그러한 경우 해당 상태(노드)를 제외하고 다음 단계로 나아가는 방식이다.

 

백 트래킹은 현재 상태(노드)에서 다음 상태(노드)로 나아갈 수 있는 모든 경우를 찾되, 그 중 유망하지 않다면?

현재에서 더이상 나아기자 않고 이전의 상태(노드)로 돌아가 다음 상태(노드)를 검사합니다.

 

여기서 더 이상 탐색할 필요 없는 상태(노드)를 제외하는 것을 가지치기(pruning) 이라고 합니다.

 

백트래킹을 사용하는 알고리즘 중 하나는 대표적으로 DFS가 있습니다.

DFS는 재귀를 통해 가능한 경로 중 유망한 경로만 찾아서 탐색을 수행한 뒤, 다시 돌아와 그 중 가장 최적의 경로를 반환합니다.

 

백트래킹을 사용해 해결할 수 있는 문제는 최적화, 열거하기, 의사결정 등등 경우가 존재합니다.

그리고 백트래킹의 시간 복잡도가 보통 '지수'라, 대부분 DP나 그리디 알고리즘으로 더 빠르게 해결할 수 있습니다.

 

 

 

 

DFS 와 백트래킹 의 차이는?

여기서 간략하게, DFS와 백트래킹을 차이를 설명하자면,

• DFS :  깊이 우선 탐색하여 모든 노드를 방문하는 것을 목표로 한다.
• Backtracking : 불 필요한 탐색을 하지 않기 위해, 유망하지 않은 경우의 수를 줄이는 것을 목표로한다.

백트래킹은 DFS에 조건이 붙어있다고 생각하면 됩니다. 해를 찾아가는 도중에, 현재 경로가 해가 될 것 같지 않다면, 그 경로를 더이상 가지않고 돌아갑니다. 이렇게 특정한 조건을 만족하는 경우만 살펴보는 것이 백트래킹입니다.

 

 

 

 

 

백트래킹의 '유망하다(Promising)' 판단은 ?

1.  유망하다 (promising)  : 해가 될 가능성이 있다면 유망하다 라고 합니다.
2.  유망하지 않다 (nonpromising) : 해가 될 가능성이 없다다면 유망하지 않다 라고 합니다.
3.  가지치기 (pruning) : 유망하지 않는 노드에 가지 않는 것을 가지치기 라고합니다.

 

 

---

 

백트래킹의 대표적인 예는 N-Queen 문제가 있는데, 해당 문제를 추후에 푼 뒤에 예제로 이 곳에다가 정리해 올리겠습니다.