백 트래킹(Back Tracking) 알고리즘

백트래킹(Back Tracking)이란?

 - 모든 경우의 수를 확인해야 할 때  => (ex) 순열

   : for문으로는 확인 불가한 경우에 사용(깊이가 달라질 때)

 

 

"깊이 우선 탐색(DFS)과 마찬가지로 스택(Stack)을 사용"

 

=> DFS는 현재 지점에서 방문할 곳이 있으면 재귀 호출을 이용해서 계속 이동하지만 모든 곳을 방문하기 때문에 목표지점이 있지 않는 경로로 빠져서 비효율적인 결과를 초래할 수도 있음.

따라서, 이와 같은 비효율적인 경로를 차단하고 목표지점에 갈 수 있는 가능성이 있는 루트를 검사하는 방법이 백트래킹(Backtracking)알고리즘!

 

 

 

 

# 백트래킹의 특징 : N이 작음(N이 10근처여야 사용가능함.)

# => 재귀함수를 사용할 때, 종료 시점 잊지말기!!!