🖥️ 참고 포스팅
📜 백트래킹(Backtracking)이란?
어떤 노드의 '유망성'을 판단한 뒤, 해당 노드가 유망하지 않은 경우, 부모 노드로 돌아가 다른 자식 노드를 찾는 방법입니다.
즉, 모든 경우의 수를 찾아보지만, 그 중에서도 가능성이 있는 경우의 수만 찾아보는 알고리즘 방법입니다.
⚠️ 브루트포스 & DFS와 비교
브루트포스
말 그대로 '모든 경우의 수' 를 찾아보는 알고리즘 입니다.
예를 들어,
"a+b+c+d = 20을 만족하는 두 수를 모두 찾아내시오.(0<=a,b,c,d<=100)"
다음과 같은 문제가 있는 경우, a=1,b=1,c=1,d=1 부터 시작하여 a=100, b=100, c=100, d=100 까지 총 1억개의 경우의 수를 모두 탐색하는 방식입니다.
장점은 모든 경우의 수를 탐색하여 100% 완전한 결과를 출력하지만, 단점은 경우의 수가 많아질수록 자원을 많이 필요로 한다는 점입니다.
백트래킹
백트래킹은 노드의 유망성을 판단한다고 했습니다. 이 말은 해당 범위 내에서 조건을 추가하여 값의 유망성을 판단한다는 의미입니다. 예를 들어, 위 예시에서 하나라도 20을 초과하는 값인 경우, 20일 가능성이 없어지게 됩니다.
따라서, 모든 수는 20 초과인 경우(21 ~ 100) 탐색하지 않습니다. 이러한 조건을 통해서 탐색하는데 필요한 자원을 많이 줄일 수 있습니다.
DFS
DFS는 그래프 완전 탐색 중 하나로, 하나의 순회 알고리즘으로 백트래킹에 사용하는 대표적인 탐색 알고리즘입니다.
즉, 백트래킹 = DFS 가 아니라, 백트래킹 방법 중 하나가 DFS인 것입니다.
이외에도 BFS 등 다양한 방법으로 백트래킹 구현이 가능합니다.
📖 예제
- N과 M (1)
