백트래킹이란 가능한 경우의 수를 모두 시도해보는데, 만약 조건에 맞지 않는다면 되돌아와 다른 경우로 시도해보는 알고리즘이다.
백트래킹의 구현
백트래킹의 구현은 크게 아래의 3가지로 나눌 수 있다.
- 선택: 현재 상태에서 시도할 수 있는 후보들을 선택한다.
- 검증: 후보들이 조건에 부합하는지 검증하고, 부합하지 않으면 다시 돌아온다.(Backtrack)
- 탈출: 원하는 결과에 도달했으면 확인하고 기록한다.
-
문제를 푸는 과정에서 발생할 수 있는 모든 경우의 수를 상태 공간 트리로 구축하고, 재귀함수를 통해 깊이 우선 탐색(DFS)로 탐색한다. 탐색하는 과정에서 조건에 부합하지 않는 노드가 있으면 그 노드가 포함된 서브 트리를 모두 배제하고 이전 노드로 돌아와 재귀적으로 다른 경로로 탐색을 계속한다.
-
재귀 함수에는 종료 조건(일반적으로 트리의 깊이)을 작성해야 무한 루프를 막을 수 있다.
-
재귀 함수를 호출할 때, 반드시 재귀 함수를 호출하기 전의 상태로 복구를 해주는 코드를 작성해야 한다.
백트래킹의 시간 복잡도
백트래킹은 가능한 모든 경우의 수를 재귀적으로 시도해보기 때문에 경우의 수가 N이라면, 최악의 경우 시간복잡도는 O(N!)이므로 보통 N의 크기가 10 내외인 경우에만 사용한다.
시간 복잡도를 줄이기 위해서는 방문 배열 visited[]를 사용해서 이미 방문한 노드를 표시하고, 재귀함수의 매개변수를 통해 탐색의 시작점이 중복되지 않게 할 수 있다.
백트래킹의 활용
백트래킹은 NQueen 문제, 순열과 조합 문제, 미로 찾기, 시뮬레이션 문제 등의 구현에 활용된다.
