[알고리즘] 백트래킹(Backtracking)

DFS와 백트래킹

깊이 우선 탐색(DFS)

DFS는 가능한 모든 경로(후보)를 탐색한다.

• 장점 : 무한히 깊은 곳을 찾아야할때 효과적이다.
• 단점 : 모든 곳을 방문하기 때문에 굳이 목표지점이 있지 않는 경로로 빠져서 비효율적인 결과를 초래할수도 있다.

=>따라서, 불필요할 것 같은 경로를 사전에 차단하거나 하는 등의 행동이 없으므로 경우의 수를
줄이지 못한다.

DFS의 비효율적인 경로를 차단하고 목표지점에 갈 수 있는 가능성이 있는 루트를 검사하는 방법이
백트래킹 알고리즘 이다!

백트래킹(Backtracking)

• 해를 찾아가는 도중, 지금의 경로가 해가 될 것 같지 않으면 그 경로를 더이상 가지 않고 되돌아 간다.
• 코딩에서는 반복문의 횟수를 줄일 수 있어 효율적이다.
• 불필요한 부분을 쳐내고 최대한 올바른 쪽으로 간다는 의미 => 가지치기
  =>가지치기를 얼마나 잘하느냐에 따라 효율성이 결정되게 된다.
  
  
  

백트래킹 기법의 유망성 판단

해가 될 가능성이 있다면 유망하다(promising)고 하며, 유망하지 않은 노드에 가지 않는 것을
가지치기(pruning) 한다.

정리

• 백트래킹은 모든 가능한 경우의 수 중에서 특정한 조건을 만족하는 경우만 살펴보는 것이다.
• 즉, 답이 될 만한지 판단하고 그렇지 않으면 그 부분까지 탐색하는 것을 하지않고 가지치기 하는 것
• DFS등으로 모든 경우의 수를 탐색하는 과정에서, 조건문 등을 걸어 답이 절대로 될 수 없는 상황을 정의하고, 그러한 상황일 경우에는 탐색을 중지시킨 뒤 그 이전으로 돌아가서 다시 다른 경우를 탐색하게끔 구현할 수 있다.

참고

• https://chanhuiseok.github.io/posts/algo-23/
• https://velog.io/@mmindoong/%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-%EB%B0%B1%ED%8A%B8%EB%9E%98%ED%82%B9BackTracking

[알고리즘] 백트래킹(BackTracking)

알고리즘 - 백트래킹(Backtracking)의 정의 및 예시문제