[알고리즘] 백트래킹이란?

백트래킹이란? (What)

탐색 알고리즘 중 하나로 DFS처럼 재귀함수로 구현됨 (DFS와 같은 순서로 탐색)

탐색을 하다가 조건에 맞지 않으면 이전 단계로 돌아가 다시 탐색을 하며 답을 찾아 나가는 알고리즘.  

 

 

언제 사용하나? (Why)

• 완전탐색처럼 하나하나 탐색해야 하는데 조건으로 가지치기를 할 수 있을 때 
•  예시
  • 최적화 문제 : 수학 혹은 컴퓨터 과학에서 모든 테스트 케이스에 대해 답을 찾는 최적의 해법을 찾는 문제
  • N-Queen 문제
  • 미로 찾기 문제

 

완전탐색과 다른점은?

완전탐색처럼 트리를 탐색하지만 조건에 맞지 않는 경우는 가지치기 함. 

 

DFS와 차이점은?

DFS는 찾는 노드가 나올 때까지 최대한으로 들어감. 백트래킹은 조건에 따라 중간에 가지치기를 하는 것이 특징. 적절하게 가지치기를 해서 필요하지 않는 노드는 탐색을 하지 않아 효율을 높여야함. 

 

어떻게 구현하나? 

1) 하나의 스텝마다 조건에 맞는지 검사

2) 조건에 맞지 않으면 더 안감 - 가지치기, 뒤로 백 

 

 

예시문제

• 경우의 수 문제
  • 중복 순열
    • K개 중 하나를 N번 선택하기-> 재귀함수로 구현한 완전 탐색이라고 볼 수 있음 
    • -> _ _ _ N개의 자리에 K개의 객체 중 하나를 뽑아서 놓는 경우의 수(순서 O)
    • K개 중 하나를 N번 선택하기(조건)
    • -> _ _ _ N개의 자리에 K개의 객체 중 하나를 뽑아서 놓는 경우의 수 (순서 O)  + 조건으로 가지치기
  • 조합
    • N개 중 M개 고르기 
      • 구현 : cnt변수를 같이 받아서 cnt가 m이 되는 조합을 고르는 방법
    • N개 중 M개를 고르기(조건)
  • 순열
    • N개 중 M개 골라서 배열하기 
      • 구현 : visited 배열 같이 받아서 구현 
• N-Queen 문제 
  • 체스판에 퀸을 배치하는 최적의 방법을 찾는 문제
• 미로 찾기 문제