Today I learned : backtracking
오늘 할 일
알고리즘3문제
바킹독의 실전 알고리즘 : 백트래킹
너무 간만에 알고리즘을 들어서 코드가 맞는지 체크를 한 번 해봐야 한다.
#include <bits/stdc++.h>
using namespace std;
int n,m;
int arr[10];
bool vis[10];
void func(int k){
if(k==m){
for(int i=0;i<m;i++)
cout<<arr[i]<<' ';
cout<<'\n';
return;
}
for(int i=1;i<=n;i++){
if(!vis[i]){
arr[k]=i;
vis[i]=1;
func(k+1);
vis[i]=0;
}
}
}
int main(void){
ios::sync_with_stdio(0);
cin.tie(0);
cin>>n>>m;
func(0);
}
연습 문제 N-Queen
#include <bits/stdc++.h>
using namespace std;
bool isused1[40];
bool isused2[40];
bool isused3[40];
int cnt=0;
int n;
void func(int cur){
if(cur==n){
cnt++;
return;
}
for(int i=0;i<n;i++){
if(isused1[i]||isused2[i+cur]||isused3[cur-i+n-1])
continue;
isused1[i]=1;
isused2[i+cur]=1;
isused3[cur-i+n-1]=1;
func(cur+1);
isused1[i]=0;
isused2[i+cur]=0;
isused3[cur-i+n-1]=0;
}
}
int main(void){
ios::sync_with_stdio(0);
cin.tie(0);
cin>>n;
func(0);
cout<<cnt;
}