[알고리즘] 백트래킹 Backtracking

백트래킹(Backtracking)

• 현재 상태에서 가능한 모든 후보군을 따라 들어가며 탐색하는 알고리즘
• 해(정답)을 찾는 도중 해가 아니어서 막히면, 되돌아가서 다시 해를 찾아가는 기법
  • 완전 탐색X
• 최적화 문제와 결정 문제를 푸는 방법
• 재귀 사용
  • 재귀의 특성상 틀리더라도 틀린 부분을 찾는 것이 힘듦

 

가지치기(Prunning)

• 해를 찾아가는 도중 해당 경로가 해가 될 것 같지 않으면 더이상 가지 않고 되돌아 가는 방식
  
  • 불필요한 부분을 쳐내고 최대한 올바른 쪽으로 감

 

접근 방식

• 모든 가능성은 하나의 트리처럼 구성할 수 있으며, 트리의 가지 중 해결책이 존재
  • 트리를 검사하기 위해 깊이 우선 탐색(DFS) 시도 → 탐색 중 오답을 만나면 이전 분기점으로 백 -> 시도해 보지 않은 해결책이 있으면 시도 -> 해결 방법이 없다면 더 이전의 분기점으로 백 -> 모든 트리의 노드를 검사해도 답을 찾지 못할 경우, 해당 문제의 해는 없음
• 보통 재귀함수로 구현
  • 하나 이상의 매개변수를 재귀의 탈출 조건으로 사용

 

백트래킹 vs 깊이우선탐색(DFS)

• DFS는 현재 지점에서 방문할 곳이 있으면 재귀 호출을 이용해 계속해서 이동, 가능한 모든 경로를 탐색
  • 불필요할 것 같은 경로를 사전에 차단할 수 없음, 경우의 수를 줄이지는 못 함
  • 모든 경우의 수를 탐색하는 과정에서, 조건문 등으로 답이 될 수 없는 상황을 정의, 그러한 상황에서 탐색을 중지시킨 뒤 이전으로 돌아가 다시 다른 경우를 탐색하게끔 구현 가능
• 백트래킹은 답이 될 만한지 판단 후 그렇지 않으면 이 후를 탐색하지 않고 가지치기를 통해 불필요한 경우의 수를 줄임

 

관련 문제

• 백준 15649번: N과 M (1) ~ (12)
• 백준 1182번: N-Queen
• 백준 1182번: 부분수열의 합

 

---

출처 : Youtube, BaaarkingDog