[Algorithm] 백트랙킹(BackTracking)

백트랙킹

백트랙킹은 가능한 모든 방법을 탐색한다. 즉, 현재 상태에서 가능한 모든 후보를 따라 후보를 다시 탐색하면서 해를 찾아나가다가 해가 아니라고 판단되면 다시 되돌아가 다른 후보를 탐색하여 해를 찾아가는 방식이다. 이는 최적화 문제와 결정문제를 푸는 방법이 된다.

 

위의 상황을 트리에 적용해보면 트리 탐색 알고리즘이라고 생각할 수 있다. 트리 탐색 알고리즘은 방식에 따라서 깊이 우선 탐색(Deep First Search, DFS), 너비 우선 탐색(Breadth First Search, BFS)으로 나눌 수 있다. 백트랙킹은 모든 경우의 수를 고려해야하기에 DFS로 구현한다. 

 

DFS(Deep First Search)

트리의 root에서 바닥에 도달할 때까지 한 쪽에서 시작하여 가능한 모든 경로를  찾는 알고리즘이다. 모든 경로를 탐색하기 때문에 모든 노드에 방문해야하고 결국 불필요한 경로를 사전에 차단할 수 없어 경로를 찾는 경우의 수를 줄이지는 못한다.

결국 백트랙킹은 DFS에서 비효율적인 경로를 차단하도록 만든 방식이다. DFS에 조건문을 집어넣어 불필요한 경로로 가는, 해가 될 수 없는 상황을 가지치기한다. 이후 이전으로 돌아가서 다시 탐색을 진행하여 해를 얻는다.

 

 

백트랙킹 예제

https://miraekwak.tistory.com/80

[BOJ] 15649번: N과 M(1)

---

출처

:https://namu.wiki/w/%EB%B0%B1%ED%8A%B8%EB%9E%98%ED%82%B9

:https://chanhuiseok.github.io/posts/algo-23/