백트래킹(Backtracking)
제약 충족 문제에서 가능한 모든 솔루션을 찾기 위해 사용되는 알고리즘 기법이다.
재귀적으로 문제를 하나씩 풀어가면서 현재 재귀를 통해 확인 중인 노드가 제한된 조건에 위배되는지 판단하고, 만약 해당 노드가 제한된 조건을 위배한다면 그 노드를 제외하고 다음 단계로 나아가는 방식이다.
각 단계에서 문제의 제약 조건을 만족하지 않으면 즉시 그 경로를 백트랙하고(가지치기) 다른 가능성을 탐색한다.
백트래킹 진행 방식
1. 솔루션 공간 탐색: 모든 가능한 해를 체계적으로 탐색한다. 이는 보통 재귀적으로 구현된다.
2. 제약 조건 검사: 현재 선택이 문제의 제약 조건을 만족하는지 검사한다. 만약 제약 조건을 위반한다면, 이 선택을 취소하고(백트랙), 다음 가능한 선택을 시도한다.
3. 솔루션 확인: 현재의 선택들이 문제의 해답을 구성할 수 있는지 확인한다. 모든 조건을 만족하는 경우, 해답으로 기록한다.
백트래킹 특징
시간 복잡도: 백트래킹 알고리즘은 모든 가능한 해를 탐색해야 할 수도 있기 때문에 일반적으로 시간 복잡도는 매우 높다. 최악의 경우, 시간 복잡도는 지수적(exponential)일 수 있다.
공간 복잡도: 재귀적 구현으로 인해 호출 스택의 크기만큼의 추가 메모리가 필요하다. 따라서 재귀의 깊이에 비례한다.
가지치기(Pruning): 불필요한 경로를 조기에 차단하여 성능을 향상시킨다. 이를 통해 솔루션 공간을 효과적으로 줄일 수 있다.
완전한 해 탐색: 백트래킹은 가능한 모든 솔루션을 시스템적으로 탐색하여, 해가 존재한다면 반드시 찾을 수 있다.
백트래킹 예시
1. N-Queen 문제
NxN 체스판 위에 N개의 퀸을 서로 공격하지 않는 방식으로 배치 한다. 퀸은 수직, 수평, 대각선 방향으로 무한정 공격할 수 있기 때문에, 이를 고려해 배치해야 한다.
접근법
1. 첫 번째 행부터 시작하여 각 행에 퀸 하나씩을 배치한다.
2. 현재 행의 모든 열에 대해 퀸을 배치해 보면서, 공격받지 않는 위치를 찾는다.
3. 만약 현재 위치에 퀸을 배치했을 때 다른 퀸과 충돌이 발생하지 않는다면, 다음 행으로 넘어가고 같은 과정을 반복한다.
4. 만약 어떤 행에서 퀸을 배치할 수 있는 위치가 없다면, 이전 행으로 돌아가 (백트래킹) 다른 위치에 퀸을 배치한다.
5. 이 과정을 모든 행에 대해 반복하여 N개의 퀸을 모두 배치할 수 있는 모든 방법을 찾는다.
2. 수도쿠
9x9 그리드에서 1부터 9까지의 숫자를 그리드의 각 행, 각 열, 그리고 9개의 3x3 서브그리드가 모두 숫자 1부터 9까지 하나씩만 포함하도록 채워 넣는 게임이다.
접근법
1. 빈 칸(0이 표시된 곳)을 찾아서 숫자를 하나씩 채워 넣는다.
2. 현재 위치에서 가능한 숫자를 시도하고, 그 숫자가 유효한지 검사한다.(같은 행, 열, 서브그리드에 동일한 숫자가 없어야 함)
3. 유효하다면 다음 빈 칸으로 넘어가고, 그렇지 않다면 다른 숫자를 시도한다.
4. 모든 칸이 유효하게 채워질 때까지 이 과정을 반복하고, 어떤 칸에서 유효한 숫자가 없다면 이전 칸으로 돌아가서 다른 숫자를 시도한다.(백트래킹)
3. 조합의 문제 (Combinatorial Problems)
주어진 집합의 요소들로부터 가능한 모든 조합을 찾아야 한다. - k개의 요소로 이루어진 조합을 n개의 요소 중에서 찾는 문제
접근법
1. 선택할 요소의 개수(k)와 전체 요소의 개수(n)를 바탕으로 조합을 구성한다.
2. 현재 요소를 선택하거나 선택하지 않는 방식으로 분기하면서 진행한다.
3. 선택한 요소의 수가 k와 일치하면 조합을 저장하고, 더 이상 진행하지 않고 이전 단계로 돌아간다.(백트래킹)
4. 모든 요소를 고려할 때까지 이 과정을 반복한다.
