[Algorithm] BackTracking / Java

BackTracking = DFS + prunning

✔ 백트래킹이란?

백트래킹은 한마디로 가지치기(prunning)를 가미한 너비우선탐색(DFS)입니다.

다시 말해서, DFS로 해를 찾아가는 과정에서 수시로 현재 경로의 유망성을 판단하여 유망하지 않음이 판단되면 더이상 나아가지 않고 이전 노드로 돌아가 다른 경로를 탐색하는 방식입니다.

 

이어서 백트래킹과 완전탐색을 비교함으로써 백트래킹의 특성을 알아보겠습니다.

✔ 백트래킹과 완전탐색(DFS)의 차이

완전탐색과 구분되는 백트래킹의 핵심적인 특성은 '가지치기'에 있습니다. 완전탐색이 모든 경로를 탐색하는 데 반해 백트래킹은 불필요한 경로를 조기에 차단함으로써 탐색 소요를 줄입니다.

따라서 백트래킹의 효율성은 가지치기의 조건에 달려있다고 볼 수 있습니다.

 

다만, 백트래킹을 사용하더라도 최악의 경우(가지치기 조건에 걸리지 않는 경우) 완전탐색과 마찬가지로 O(N!)의 시간 복잡도를 가질 수 있습니다.

* N개의 노드가 있을 때, 모든 경로를 탐색하는 데에는 N! 가지의 경우의 수가 있다.

 

✔ 백트래킹의 과정

백트래킹의 탐색은 기본적으로 DFS와 마찬가지로 트리 구조로 이루어져있습니다.

부모노드에서 자식노드로 이동하는데, 이때 특정 조건을 만족하는 경우에만 자식노드로 이동하고 그렇지 않은 경우에는 다시 부모노드로 돌아가 다른 자식노드를 탐색합니다.

 

 

---

 

🚩 참고

대표적인 백트래킹 문제인 N-Queen 문제의 풀이를 소개합니다.

https://dev-green.tistory.com/109

[백준] 9663. N-Queen / Java