백트래킹(Backtracking)

백트래킹(Backtracking) 이란

백트래킹 이란 모든 경우의 수를 전부 고려하는 알고리즘 이다.

조금 더 자세하게 말하자면 현재 상태에서 가능한 모든 후보군을 따라가며 해결책에 대한 후보를 구축해 나아가다 가능성이 없다고 판단되면 즉시 후보를 포기하면서 정답을 찾아가는 범용적 알고리즘이라고 한다.

상태 공간을 트리로 나타낼 수 있을 때 적합한 방식이다. 일종의 트리 탐색 알고리즘이라고 봐도 된다.

 

백트래킹을 사용해 해결할 수 있는 문제는 주로 검색, 의사 결정, 최적화, 열거하기 등의 문제가 있다.

사실 백트래킹은 사용 가능한 경우가 많지만 시간복잡도가 보통 $2^n$ 이기 때문에

대부분의 문제는 동적 프로그래밍 또는 그리디 알고리즘 등으로 더 빠르게 해결할 수 있다.

그렇다고해서 백트래킹을 사용하지 않는 것이 아니라 여전히 백트래킹을 사용해서 풀어야 하는 문제들이 있다.

백트래킹의 문제 예로는 n-퀸 문제, 외판원 문제, 스도쿠 퍼즐 등이 있다.

 

백트래킹 방식에 따라 3가지로 구분할 수 있다.

• 깊이 우선 탐색 (Depth First Search, DFS)
• 너비 우선 탐색(Breadth First Search, BFS)
• 최선 우선 탐색(Best First Search/Heuristic Search)

 

 

백트래킹 연습 문제

백트래킹 문제를 연습해볼 수 있는 링크는 다음과 같다.

아래의 문제 말고도 다양한 문제를 풀어보면서 익히면 좋을 것 같다.

 

• 백준 알고리즘 문제 링크

https://www.acmicpc.net/problem/15649

15649번: N과 M (1)

https://www.acmicpc.net/problem/9663

9663번: N-Queen