백트래킹 (BackTracking)
백트래킹 알고리즘이란 퇴각 검색이라고도 불리며, 이는 한정 조건 을 가진 문제를 풀려는 전략이다.
쉽게 설명해서 어떤 문제를 푸는데 있어 모든 경우의 수를 시도하여 문제의 정답을 찾아나간다. 하지만 백트래킹에서는 한정 조건 에서의 모든 경우의 수를 시도하는 것이기 때문에 실제로 상당한 경우의 수들이 배제되기 때문에 단순 다중 for문 보다는 빠르게 해결되는 경우가 많다.
즉, DFS 를 사용하여 만약 조건에 맞지 않으면, 그 즉시 중단하고 이전으로 돌아가여 다시 확인하는 것을 반복하면서 원하는 조건을 찾는 알고리즘이다.
구현은?
보통 백트래킹의 구현은 BFS 나 DFS 와 함께 구현한다. 모든 경우의 수에서 한정 조건 을 만족하는 경우를 탐색하는 것이기 때문에, 완전 탐색 기법인 BFS 와 DFS 가 모두 구현이 가능하다.
하지만 백트래킹의 특성에서 한정 조건에 부합하지 않다면(Node가 유망하지 않다면) 이전 수행(이전 Node)으로 돌아와야하기 때문에 BFS 보다 DFS 의 구현이 더 편하다.
구현할 때 가장 중요한 것이 한정 조건 이다.
한정 조건 을 걸어 완전 탐색에서 유망하지 않은 시도를 걸러내는 것이 바로 백트래킹의 본질이다. 그럼 한정 조건 이 무엇인지 어떤식으로 동작하는지 예제를 통해서 알아보자.
•
Promising - 해당 루트가 조건에 맞는지를 검사하는 기법
•
Pruning(가지치기) - 조건에 맞지 않으면 포기하고, 다른 루트로 바로 돌아서서, 탐색의 시간을 절약하는 기법
→ 백트래킹은 트리 구조를 기반으로 DFS로 깊이 탐색을 진행하면서, 각 루트에 대해 조건에 부합하는지 체크(Promising-솔루션이 될 수 있는지), 만약 해당 트리에서 조건에 맞지 않는 노드는 더 이상 DFS로 깊이 탐색을 진행하지 않고, 가지를 쳐버린다(Pruning - 이 노드 아래의 모든 값들은 탐색할 필요가 없다)
예제) N-Queen 문제
•
NxN 체스판에 N개의 퀸을 놓을 때, 서로가 공격을 하지 못하게 만들 수 있는 경우의 수
설계
•
퀸이 서로 공격을 하지 못하려면, 같은 가로, 세로, 대각선 상에 있으면 안된다 (Promising)
•
Backtracking을 이용해서 모든 경우의 수를 계산하는데 서로가 공격하는 조건을 만족 시에 가지치기(Pruning)를 한다.
•
만약 퀸의 수가 N이면 경우의 수 하나를 더해준다.
•
배열을 하나 만들어서 가로, 세로 중 하나를 고정 시켜준다.