백트래킹이란?
해를 찾아가는 도중 지금의 노드가 해가 될 만한지 판단한 후 유망하지 않다고 결정되면 그 노드의 이전(부모)로 돌아가서 다음 자식 노드로 가는 기법을 말한다. 가지치기 라고도 하는데, 불필요한 부분을 쳐내고 최대한 올바른 쪽으로 간다는 의미이다.
기본적으로 완전 탐색에 기본 아이디어가 있다. 그러나 DFS 는 모든곳을 방문하기 때문에 굳이 목표 지점이 있지 않는 경로까지도 가므로 비효율적인 결과를 초래할 수 있다.
그래서 이와 같은 비효율적인 경로를 차단하고 목표지점에 갈수있는 가능성이 있는 루트를 검사하는 방법이 백트래킹 알고리즘으로, DFS에 가지치기 (Pruning) 를 통해 가도되지 않는 루트는 고려하지 않고 탐색하는 완전탐색 기법 이다.
다른 말로 DFS와 백트래킹의 차이점은 DFS는 가능한 모든 후보를 탐색하여 불필요한 경로를 사전에 차단할 수 없다 는 점이다.
시간복잡도
N^N: 중복이 가능N!: 중복이 불가
Tip
-
백트래킹 문제는 N이 10이하로 작을 것이다. (시간복잡도가 2억을 넘지 않아야 하므로)
-
또한 재귀함수를 사용할 때 종료 시점을 잊지 말자
15649 N과 M (1)
문제 접근
백트래킹의 기본적인 틀(?)을 알 수 있는 문제라고 한다.
백트래킹 재귀함수 안에서 for문을 돌면서 숫자를 선택한다. (이 때 방문 여부를 확인한다) 그리고 재귀함수에서 M개를 선택할 경우 출력해준다.
순서가 상관없는 '조합'의 개수를 구하는 문제이므로 DFS를 활용하여 풀이가 가능하다. 각 숫자는 순열에서 딱 한번만 사용되므로, 각 숫자를 인덱스로 가지는 bool형 배열인 visited를 선언하고, 해당 숫자를 뽑았는지 유무를 저장한다. 숫자를 앞에서부터 한개씩 뽑아가면서 visited가 M개만큼 true가 되면 출력을 해주는 재귀함수를 활용하면 된다.
#include <iostream>
#define MAX 9
using namespace std;
int n,m;
int arr[MAX];
bool visited[MAX];
void dfs(int cnt){ // 현재 위치
// 재귀함수의 종료 조건
if(cnt == m){ // 목표값 M까지 도달했다면
for(int i = 0; i < m; i++){
cout << 1 + arr[i] << ' ';
}
cout << "\n";
return;
}
// 목표값 M에 도달하지 않았다면
for(int i = 0; i < n; i++){
if(!visited[i]){
visited[i] = true;
arr[cnt] = i;
dfs(cnt + 1); // M까지 도달하기 위해 더 깊게 들어간다
visited[i] = false; // 백트래킹
}
}
}
int main(){
cin >> n >> m;
dfs(0);
}