백트래킹(Backtracking) 알고리즘

그림 출처 - 위키백과

설명

DFS를 기반으로 생성된 알고리즘으로, 기존 DFS는 모든 경우의 수를 찾아가기 때문에 불필요한 탐색이 존재하여 이 부분이 문제가 되는 경우가 있었다. 때문에 이를 보완하기 위해서 나온 알고리즘으로, 현재 탐색을 진행하고있는 루트가 이미 실패가 예정된 루트라면 해당 루트를 종료하고 더 이상 그 루트를 통하여 탐색을 진행하지 않고 이전으로 돌아가는 것을 백트래킹이라고 칭한다. 때문에 현재 루트의 가능성을 판단하는 조건이 잘 짜여질수록 효율이 올라가게 된다.

보통 DFS를 사용하는 문제에서, 완전탐색 시 경우의 수가 너무 많아지는 문제에 대하여 조건을 걸어서 루트를 줄이는 역할을 한다. 

 

대표적인 백트래킹 문제인 N-Queen에서의 예시

문제를 요약하자면 퀸이 서로 겹치지 않게 NxN크기의 판에 N개의 퀸을 놓을 수 있는 수를 찾는 문제이다.

기본적인 n퀸의 경우의 수는 n^n이다. n의 최대값이 10임을 고려하더라도 10^10인 10,000,000,000개의 경우의 수가 생기는데, 백트래킹을 사용하여 만약 어떤 가로줄에 퀸이 놓이지 못하는 경우가 생긴다면? 이라는 조건을 추가해줌으로써, 경우의 수를 대폭 줄일 수 있다. (문제 자체가 모든 가로줄에 퀸이 하나씩 있어야하기 때문에 현재 가로줄에 퀸을 배치할 수 없다면 다음을 탐색할 필요 없이 해당 루트를 종료함)