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

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

* 백트래킹이란?

 모든 경우의 수를 전부 고려하는 알고리즘이다. 일종의 트리 탐색 알고리즘이라고 봐도 된다. 구조적으로 깊이우선탐색을 기반으로 한다. 즉, DFS의 구조를 적용할 수 있는 문제에 적용될 수 있다. 

 백트래킹을 쉽게 설명하자면 어떤 노드의 유망성을 점검하고 유망하지 않으면 그 노드의 부모 노드로 돌아간 후 다른 자손의 노드를 검색하는 것을 말한다. 즉, 스택에 자식노드를 넣기 전에 유망한지(해답이 될 가능성이 있는지) 확인하고 스택에 넣음을 말한다.

* 백트래킹과 DFS의 차이

 백트래킹의 경우 가지치기가 일어나므로 원시적인 방법으로 모든 경우의 수를 확인하는 알고리즘은 아니다.

 [참조] https://www.slideshare.net/JaehoSeok/0521-8051381

* 예시

 가장 흔하게 접할 수 있는 4-Queens Problem

 서로 상대방을 위협하지 않도록 4*4 체스판에 위치시키는 문제인데 퀸의 위치를 트리화 시켜 유망할 경우 스택에 넣고 그렇지 않다면 스택에 넣지 않음으로써 수행 효율을 높인다. 아래 블로그에 상세히 설명되어있어 잘 이해할 수 있었다.

 [참조] http://idea-sketch.tistory.com/29