백트래킹 (Backtracking) 알고리즘이란?

백트래킹이란?

해를 찾아가는 도중, 지금의 경로가 해가 될 것 같지 않으면 그 경로를 더이상 가지 않고 되돌아가는(Backtracking) 기법을 말한다.  -> 반복문의 횟수를 줄여서 효율적이다!!!

 

좀더 정확하게 말하자면 어떤 노드의 유망성, 즉 해가 될 만한지 판단한 후 유망하지 않다고 결정되면 그 노드의 이전(부모)로 돌아가(Backtracking) 다음 자식 노드로 가는 기법을 말한다.

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

 

기본적으로 백트래킹은 '가능한 모든 방법을 탐색한다'(완전 탐색 기법) 에 기본 아이디어가 있다. 대표적인 완전 탐색 방법으로는 DFS (Depth First Search, 깊이 우선 탐색) 이 있다. 

하지만 DFS 는 모든곳을 방문하기 때문에 굳이 목표지점이 있지 않는 경로로 빠져서 비효율적인 결과를 초래할수도 있다. 그래서 이와 같은 비효율적인 경로를 차단하고 목표지점에 갈수있는 가능성이 있는 루트를 검사하는 방법이 백트래킹 알고리즘이다. 백트래킹은 DFS에 가지치기 (Pruning) 를 통해 가도되지 않는 루트는 고려하지 않고 탐색하는 완전탐색 기법이다.

 

따라서 백트래킹 알고리즘은 DFS를 하다가 유망한 노드를 검색하고 아니다면 Backtracking하는 방식으로 구현된다.

 

*DFS와 백트래킹의 다른점은 DFS는 가능한 모든 후보를 탐색하여 불필요한 경로를 사전에 차단할 수 없다는 점이다.

 

 

 

 

 

참고 - https://thd0011.tistory.com/19

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