백트래킹이란?
탐색을 하는데 (dfs와 탐색법이 비슷하다) 만약 조건에 맞지 않는다면 중지하고 이전으로 돌아가서 원하는 조건을 찾는 방식!
예를들어
겹치지 않는 홀수만 가지고 오름차순 세자리를 만드는 문제라 하면? ( 135, 195 등등)
첫번째 자리 1부터 9까지 하나씩 넣어봄
첫번째로 1이 왔다고 치자
1 _ _
두번째자리 아무거나 넣어봄
1 2 _
여기서 2는 홀수가 아니기 때문에 종료하고 다시 1 _ _ 로 돌아가는 것이 백트래킹이다!
( 1 2 3, 1 2 4, 1 2 5 등등은 시도해볼 필요도 없다 , 2가 짝수이므로)
다시 1 _ _ 로 돌아가서 이번에는 3을 넣고 1 3 _ 로 돌려서 조건에 맞는걸 계속해서 찾아간다
dfs와 다른 점은 dfs는 모든 경우를 탐색하므로 1 2 3까지 간 후에 조건에 안맞음을 확인하는데,
백트래킹 이용 시 1 2 에서부터 자르므로 탐색 횟수가 줄어들게 된다
N과M 시리즈부터 다 풀어보기!!
#include <stdio.h>
int array[10];
int visited[10];
int m,n;
void back(int x){ //x번째 자리 수를 결정한다
if(x==m+1){
for(int i=1;i<=m;i++){
printf("%d ",array[i]);
}
printf("\\n");
}else{
for(int i=1;i<=n;i++){
if(visited[i]==0){
visited[i]=1;
array[x]=i;
back(x+1);
visited[i]=0;
}
}
}
}
int main(){
scanf("%d %d",&n,&m);
back(1);
}