[Algorithm] 백트래킹(BackTracking)

백트래킹?

백트래킹은 해를 찾는 도중 해가 아니어서 막히면 되돌아가서 다시 해를 찾아가는 기법을 말한다.

최적화 문제와 결정 문제를 푸는 방법이 된다.

 

모든 경우의 수를 전부 고려하는 알고리즘 상태공간을 트리로 나타낼 수 있을 때 적합한 방식이다. 일종의 트리 탐색 알고리즘이라고 봐도 된다.
방식에 따라서 깊이우선탐색(DFS)과 너비우선탐색(BFS), 최선 우선 탐색(Best First Search/HeuristicSearch)이 있다.
모든 경우의 수를 고려해야 하는 문제라면, DFS가 낫다.
BFS로도 구현이 물론 가능하지만, BFS는 큐의 크기가 매우 커질 수 있고 속도도 차이가 없기 때문에 경우의 수 구하기는 일반적으로 DFS가 편리하다.

출처: 나무위키

 

DFS & 백트래킹

백트래킹은 DFS를 사용하여 조건에 맞지 않으면 그 즉시 중단하고 이전으로 돌아가서 다시 확인하는 것을 반복하면서 원하는 조건을 찾는 알고리즘이다.

 

DFS

DFS는 가능한 모든 경로를 탐색한다. 따라서 불필요할 것 같은 경로를 사전에 차단하거나 하는 등의 행동이 없으므로 경우의 수를 줄이지 못한다.

따라서 N! 가지의 경우의 수를 가진 문제는 DFS로 처리가 불가능할 것이다.

 

백트래킹(Backtracking)

해를 찾아가는 도중, 지금의 경로가 해가 될 것 같지 않으면 그 경로를 더 이상 가지 않고 되돌아간다.

이를 가지치기라고 하는데, 불필요한 부분을 쳐내고 최대한 올바른 쪽으로 간다는 의미다.

 

일반적으로, 불필요한 경로를 조기에 차단할 수 있게 되어 경우의 수가 줄어들지만, 만약 N!의 경우의 수를 가진 문제에서 최악의 경우에는 여전히 지수함수 시간을 필요로 하므로 처리가 불가능 할 수도 있다.

따라서, 가지치기를 얼마나 잘하냐느에 따라 효율성이 결정된다.

 

가지치기는 간단히 말해서 DFS 등을 통해 모든 경우의 수를 탐색하는 과정에서, 조건문 등을 걸어 답이 될 수 없는 상황의 경우 탐색을 중지시키고 다른 길을 탐색하도록 하는 것이다.

 

백트래킹에 능숙해지려면 많은 문제를 풀면서 여러 상황에 익숙해져야 한다. 많은 시간초과가 나고 절망해봐야한다.

열심히 그래프 문제를 풀면서 능력을 키워보자

 

N-Queen 문제

백트래킹의 대표적인 문제로 노드를 탐색하며 해당 노드의 유망성을 판단하여 유망한 노드이면 서브트리로 이동하고 그렇지 않으면 백트래킹을 수행하는 방식으로 해결 할 수 있다.

[baekjoon] 9663 N-Queen

9663번: N-Queen