백트래킹(Back Tracking)

백트래킹(Backtracking)은 모든 가능한 해를 탐색하는 과정에서, 현재 상태에서 더 이상 해를 찾을 가능성이 없는 경우 되돌아가서 이전 상태로 돌아가는 기법이다. 이 방법은 최적화 문제와 조합적 탐색 문제에서 사용되는 경우가 많다.

---

백트래킹의 기본 개념

• 문제 해결을 위한 상태 공간 트리:
  백트래킹은 상태 공간 트리를 탐색하면서 해결책을 찾는다. 상태 공간 트리는 가능한 모든 상태(해결책 후보)를 나타내는 트리를 말한다. 백트래킹은 이 트리의 모든 노드를 탐색하여 해를 찾는 방법이다.
• 가능성 없는 해의 가지치기(Pruning):
  백트래킹의 핵심은 겹치거나 가능성이 없어보이는 경로를 탐색하지 않고 이를 더이상 탐색하지 않는 것다. 이를 가지치기(Pruning)이라고 부른다. 더이상 탐색하지 않아도 되는 경로는 현재 경로를 확장해도 유효한 해를 찾을 수 없는 경우를 말한다.
• 재귀적 탐색:
  백트래킹은 재귀적으로 상태 공간 트리를 탐색한다. 각 단계에서 가능한 선택지를 하나씩 시도하고, 선택한 결과가 해답이 될 수 없는 경우 이전 단계로 돌아가 다른 선택지를 시도한다.

---

이제 백트래킹의 기초 문제인 N-Queen을 풀어보자.

N-Queen

2024.08.09 - [알고리즘 문제풀이/백트래킹] - 백준 9663 : N-Queen

백준 9663 : N-Queen

 

 

4-Queen 문제의 상태공간트리 일부를 예로 들어보자.

• 각 레벨은 체스판의 행을 나타낸다.
• 각 노드는 그 행에 퀸을 어느 열에 배치했는지를 나타낸다.

이 트리는 탐색하면서 조건에 맞지 않는 노드들을 "X"로 가지치기하는 방식으로 작동한다.