DFS vs. 백트래킹
DFS (Depth-First Search)
깊이 우선 탐색 DFS는 가능한 모든 경로(후보)를 탐색한다. 불필요할 거 같은 경로를 사전에 차단하지 않기 때문에 경우의 수를 최적으로 줄이지 못한다. 따라서 N!의 경우의 수를 가지는 문제는 DFS로 처리하지 못할 가능성이 매우 크다.
백 트래킹 개념
백트래킹은 해를 찾아가는 도중에 지금의 경로가 해가 될 거 같지 않으면, 더 이상 깊이 들어가지 않고 이전 단계로 다시 돌아간다.
이를 가지치기라고 하는데, 불필요한 부분을 쳐내고 최대한 올바른 방향으로 나아가는 방식이기 때문에 DFS보다 효율적이다. 하지만, N!의 경우의 수를 가진 최악의 문제에서는 여전히 지수함수의 시간복잡도가 걸려서 처리가 불가능할 수도 있다. 따라서, 가지치기를 얼마나 잘하느냐에 따라 효율성이 결정된다.
정리하자면, 백트래킹은 모든 가능한 경우의 수 중에서 특정한 조건을 만족하는 경우만 살펴보는 것이다! 즉, 답이 될만한 가능성이 없으면 더 이상 탐색을 진행하지 않고 가지치기를 하면서 최적해를 구하는 것이다.
주로 문제풀이에서는 DFS 등으로 모든 경우의 수를 탐색하는 과정에서, 조건문을 걸어서 답이 절대로 될 수 없는 상황을 정의하고, 그런 상황일 때는 탐색을 중지시킨 뒤 다시 이전 단계로 돌아가서 다른 경우를 탐색하도록 구현할 수 있다.
한 가지 예시로 n개 중에 순서를 고려하지 않고 r개를 선택하는 조합 코드를 보자. DFS로 깊이 있게 탐색하다가 r개를 모두 선택한 경우에는 현재 가지에 대한 탐색을 종료한다. 그리고 다음 경우의 수에 대한 탐색을 위해 상태를 복구하고 다시 재귀 호출을 반복한다. 따라서 조합도 백트래킹의 예시라고 볼 수 있다.
백트래킹이란 해를 찾는 도중에 막히면 더 이상 깊이 들어가지 않고, 이전 단계로 되돌아가서 해를 찾아나가는 기법을 말한다. 최적화 문제와 결정 문제를 푸는 방법이 된다고 한다.
백트래킹의 유망성 판단
어떤 노드의 유망성, 즉 해가 될 만한지 판단한 후에 유망하지 않다고 결정되면, 그 노드의 이전 노드 (부모)로 돌아가 (Backtracking) 다음 자식 노드로 이동한다.
해가 될 만한 가능성이 있으면 유망하다 (promising)고 하며, 유망하지 않은 노드에 가지 않는 것을 가지치기 (pruning)라고 한다.
예제
해당 문제 참고
핵심 아이디어
- 1부터 n중에 하나를 선택한 뒤
- 다음 1부터 ~ n 선택할 때, 이미 선택한 값이 아닌경우 선택한다.
- M개를 선택할 경우 프린트
백트래킹 시간 복잡도
-
N^N : 중복이 가능하다. N = 8까지 가능하다.
-
N! : 중복이 불가, N = 10까지 가능하다.
# 1. 아이디어 :
# - 백트래킹 재귀함수 안에서, for문을 돌면서 숫자를 선택한다.(이때 방문여부 확인)
# - 재귀함수에서 M개를 선택할 경우 print
# 2. 시간복잡도
# - N! > 가능
# # 3. 자료구조
# - 결과값 지정 int[]
# - 방문여부 확인 bool[]
import sys
input = sys.stdin.readline
N,M = map(int, input().split())
rs = []
chk = [False] * (N+1)
# rs = [1,2,3,,,] 라고 할 때, chk = [False ~~~ N-1개 까지 간다.] 0~N-1 작업이 귀찮으니 이렇게 설정한 것.
def recur(num):
if num == M:
print(' '.join(map(str,rs)))
return
for i in range(1,N+1):
if chk[i] == False:
chk[i] = True
rs.append(i)
recur(num+1)
chk[i] = False
rs.pop()
recur(0)
(2) c언어
void dfs(int cnt, int idx) { // 현재까지의 결과, 탐색을 진행할 인덱스
// r개를 선택한 경우
if(cnt == r) {
// 결과 처리 후 현재 가지에 대한 탐색 종료
return;
}
// r개를 선택하지 않은 경우 재귀 호출 반복
for(int i = idx; i < n; i++){
if(!selected[i]){
selected[i] = true; // 상태 변화
dfs(cnt + 1, i); // 재귀 호출
selected[i] = false; // 다음 경우의 수를 위해 상태 복구
}
}
}