백트랙킹 기법 정리

백트랙킹(backtracking)이 무엇인가? 뭐 탐색을 하면서 그냥 필요없는 경로는 손절치고 가지치기하는 알고리즘이다. DFS랑 유사하다 이정도로 대충 알고있었다. 따라서 이번에 공부하면서 정리해보려한다.  

그냥 넣은 그림

✏️ Backtracking

정의는 이렇다. '해를 찾는 도중에 해가 아니어서 막히면 다시 되돌아가서 다시 해를 찾는 기법.'

이걸 가지치기(pruning)이라고 하는데 가지치기를 얼마나 잘하느냐에 따라 효율성이 결정된다. 

 

구현방식?

DFS등으로 모든 경우의수를 탐색하는 과정에서 조건문등으로 답이 절대 될 수 없는 상황을 정의하고 그런 상황에서는 탐색을 중지시키고 다시 처음으로 가서 다른 경우를 탐색하게끔 구현할 수 있다.

 

• 트리에 대해서 DFS 실시
• 각 노드가 유망한지(promising) 점검
• 해당 노드가 유망하지 않다면 부모노드로 돌아가서 검색을 계속.

 

대표적인 문제로는 N-Queen 문제가 있다. 백트랙킹으로 해결해보고 다시 돌아오겠다.

* NQueen 문제: N*N 사이즈의 체스판에서 모든 행에 대해 각 행마다 하나의 퀸이 존재하도록 퀸을 배치하는 문제