[알고리즘] 백트래킹(Backtracking) 가지치기 기법 (Java)

백트래킹 Backtracking

백트래킹은 조건 만족 문제(CSP; Constrain Satisfication Problems)를 해결하기 위해 사용하는 알고리즘이다.

 

이는 어떤 조합을 탐색하는데 무작정 그리디하게 모든 곳을 탐색하는 것이 아니라 조건에 만족하지 않으면 왔던 길을 되돌아가 조건이 만족하는 부분에 한해 완전 탐색하는 것이다.

 

❐ 백트래킹의 대략적인 흐름은 다음과 같다.

     1. 어떤 노드의 유망성(탐색 가능성) 체크

            1-1. 탐색 가능하면 그대로 탐색

            1-2. 탐색이 가능하지 않으면 그 노드의 부모노드로 되돌아간 후 다른 자식노드를 탐색 BACK! - ✂️가지치기 

 

그래서 백트래킹(되추적)이라고 불리는 것이다.

 

DFS + 백트래킹?

DFS는 모든 노드를 방문하고자 하는 경우에 주로 사용한다.

 

DFS 탐색 과정을 보면 불필요한 부분을 사전에 차단하지 않고 한 부모 노드를 stack방식으로 자식 노드를 최대한 깊이 탐색한다. 그래서 인접한 부분부터 탐색하는 BFS에 비해 DFS는 탐색속도가 느리다는 단점을 가지고 있다.

 

그래서 탐색에 조건이 있는 경우 DFS탐색 + 백트래킹을 많이 사용한다. 한 부모 노드를 깊이 탐색하면서 불필요한 부분을 가지치기하여 효율성을 높여주기 때문이다. 

 

☛ 물론 DFS외에도 모든 경우를 탐색하는 문제가 있으면 조건문이나 break, continue같은 방법을 사용하여 유망성을 체크하여 조건에 해당하지 않으면 가지치기하게끔 많이 구현한다.

 

---

그럼 이제 백트래킹의 가장 대표적인 예제 N-Queen을 풀어보자

[BOJ] 백준 9663번 N-Queen 백트래킹 (Java) - DOT CODING