백트래킹(Backtracking): 해를 찾는 도중에 지금의 경로가 해가 되지 않을 경우 그 경로를 더이상 가지 않고 되돌아오는 것!
-> 모든 가능한 경우의 수 중 특정 조건을 만족시키는지 확인
-> 특정 조건 만족안하면 탐색 X
-> DFS등에서 모든 경우의 수를 탐색하는 과정에서 같이 사용하여 더 이상 아니면 그 이전으로 돌아가서 다시 탐색
-> 조합과 관련된 문제는 백트레킹!
-> 자기 자신을 호출하는 재귀함수를 주로 이용, 탈출 조건 잘 써야함!
15650 N과 M(2)
-> 중복 안됨
-> 오름차순
#include <stdio.h>
int arr[11];
void ascend(int front,int n, int m, int cnt)
{
for(int i=front;i<=n;i++)
{
arr[cnt]=i;
if(cnt!=m)
ascend(i+1,n,m,cnt+1);
else
{
for(int j=1;j<=m;j++)
{
printf("%d ",arr[j]);
}
printf("\n");
}
}
}
int main(void)
{
int n,m,cnt=1;
scanf("%d %d",&n,&m);
for(int i=1;i<=n;i++)
{
arr[1]=i;
if(cnt!=m)
ascend(i+1,n,m,cnt+1);
else
{
printf("%d\n",i);
}
}
}
15652 N과 M (4)
-> 중복이 됨
-> 오름차순 정렬
#include <stdio.h>
int arr[11];
int save[11];
void ascend(int front,int n, int m, int cnt)
{
for(int i=front;i<=n;i++)
{
arr[cnt]=i;
if(cnt!=m)
ascend(i,n,m,cnt+1);
else
{
for(int j=1;j<=m;j++)
{
printf("%d ",arr[j]);
}
printf("\n");
}
}
}
int main(void)
{
int n,m,cnt=1;
scanf("%d %d",&n,&m);
/*for(int i=1;i<=n;i++)
{
scanf("%d",&save[i]);
for(int j=i;j>1;j--)
{
if(save[j]<save[j-1])
{
int tmp=save[j];
save[j]=save[j-1];
save[j-1]=tmp;
}
else
break;
}
}
*/
for(int i=1;i<=n;i++)
{
arr[1]=i;
if(cnt!=m)
ascend(i,n,m,cnt+1);
else
{
printf("%d\n",arr[1]);
}
}
}
15654 N과 M (5)
-> 중복 안됨
-> 오름차순이 아니기 때문에 지나갔는지 안지나갔는지 확인을 해야함
#include <stdio.h>
int arr[11];
int save[11];
void ascend(int n, int m, int cnt)
{
for(int i=1;i<=n;i++)
{
// 기존에 중복을 피하기 위한 코드
int d=0;
for(int j=1;j<=cnt;j++)
{
if(save[i]==arr[j])
d=1;
}
if(d==1)
continue;
//중복이 없다-> arr배열에 저장
arr[cnt]=save[i];
if(cnt!=m){
ascend(n,m,cnt+1);
arr[cnt+1]=0;
}
else
{
for(int j=1;j<=m;j++)
{
printf("%d ",arr[j]);
}
printf("\n");
}
}
}
int main(void)
{
int n,m,cnt=1;
scanf("%d %d",&n,&m);
//save[]배열에 저장
for(int i=1;i<=n;i++)
{
scanf("%d",&save[i]);
//배열에 저장하자마자 정렬
for(int j=i;j>1;j--)
{
if(save[j]<save[j-1])
{
int tmp=save[j];
save[j]=save[j-1];
save[j-1]=tmp;
}
else
break;
}
}
for(int i=1;i<=n;i++)
{
arr[1]=save[i];
if(cnt!=m){
ascend(n,m,cnt+1);
arr[2]=0;
}
else //출력
{
printf("%d\n",arr[1]);
}
}
}
15657 N과 M (8)
-> 중복 가능
-> 비내림차순
-> 단 N개의 수를 받아 정렬을 시켜줘야한다는 점에서 N과 M (4) 와 다름!
#include <stdio.h>
int arr[11];
int save[11];
void ascend(int front,int n, int m, int cnt)
{
for(int i=front;i<=n;i++) //중복과 관련된 처리를 안해줘도 됨!
{
arr[cnt]=save[i];
if(cnt!=m){
ascend(i,n,m,cnt+1); //비내림차순이므로 ascend 맨 처음 변수가 front가 아닌 i가 되어야한다
//현재상태보다 같거나 커야하므로 i를 써줘야함!
}
else
{
for(int j=1;j<=m;j++)
{
printf("%d ",arr[j]);
}
printf("\n");
}
}
}
int main(void)
{
int n,m,cnt=1;
scanf("%d %d",&n,&m);
//save[]배열에 저장
for(int i=1;i<=n;i++)
{
scanf("%d",&save[i]);
//배열에 저장하자마자 정렬
for(int j=i;j>1;j--)
{
if(save[j]<save[j-1])
{
int tmp=save[j];
save[j]=save[j-1];
save[j-1]=tmp;
}
else
break;
}
}
for(int i=1;i<=n;i++)
{
arr[1]=save[i];
if(cnt!=m){
ascend(i,n,m,cnt+1); //front가 아닌 i!
}
else //출력
{
printf("%d\n",arr[1]);
}
}
}