가령 1,0에 퀸을 놓으면 1,0이 포함된 행과 열 그리고 두 개의 대각선에 퀸을 놀 수 없다.
이때 1,2는 둘 수 없는 위치이다. 그런데 2, 2는 둘 수 있는 위치이고, 2,2에 퀸을 두고 또 2,2를 둠으로써 둘 수 없는 위치를 잡고 나서 재귀를 빠져나올 때, 2,2의 행과 열 그리고 두 대각선의 bool 값을 모두 변경해버리면 1,1가 막고 있었던 것이 풀리게 되어서 제대로 된 연산이 되지 않는다.
따라서 좌표 하나하나를 관리할 게 아니라, 열과 행 그리고 대각선들로 사용중 여부를 관리하는 배열을 잡아야 한다.
#include<iostream>
using namespace std;
int N, m[15][15];
bool isused[15][15];
int cnt = 0;
void usage(int i, int j, bool ctr) {
isused[i][j] = ctr;
if (ctr) {
printf("퀸위치: %d %d'\n", i, j);
}
for (int k = 0; k < N; k++) {
isused[i][k] = ctr;
isused[k][j] = ctr;
}
for (int l = 0; l < N; l++) {
for (int m = 0; m < N; m++) {
if (l + m == i + j) isused[l][m] = ctr;
if (l - m == i - j) isused[l][m] = ctr;
}
}
}
void func(int k) {
if (k == N+1 ) {
cnt++;
return;
}
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
if (!isused[i][j]) {
usage(i, j, true);
printf("%d %d에 퀸추가\n", i, j);
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
cout << isused[i][j] << ' ';
}cout << '\n';
}
cout << '\n'<<'\n';
func(k + 1);
//isused[i][j] = false;
usage(i, j, false);
printf("%d %d에 퀸제거\n", i, j);
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
cout << isused[i][j] << ' ';
}cout << '\n';
}
cout << '\n' << '\n';
}
}
}
}
int main(void) {
cin >> N;
func(1);
cout << cnt << '\n';
return 0;
}
#include<iostream>
#include<algorithm>
using namespace std;
int num[9], arr[9];
int n, m;
void func(int k) {
if (k == m + 1) {
for (int i = 1; i <= m; i++)
cout << arr[i] << ' ';
cout << '\n';
return;
}
for (int i = 1; i <= n; i++) {
if (arr[k - 1] > num[i]) continue; //k가 1이면 arr[] = 0 이라서 상관X
else {
arr[k] = num[i];
func(k + 1);
}
}
}
int main(void) {
cin >> n >> m;
//n개 가지고 길이 m
for (int i = 1; i <= n; i++)
cin >> num[i];
sort(num + 1, num + 1 + n);
func(1);
return 0;
}
#include<iostream>
#include<algorithm>
using namespace std;
int N, M, num[8], arr[8];
void func(int k) {
if (k == M + 1) {
for (int i = 1; i <= M; i++) {
cout << arr[i] << ' ';
}
cout << '\n';
return;
}
for (int i = 1; i <= N; i++) {
arr[k] = num[i]; //k번째 자리로 i번째 숫자 선택
func(k + 1); //k+1번째 자리 정하기
}
}
int main(void) {
cin >> N >> M;
for (int i = 1; i <= N; i++)
cin >> num[i];
sort(num + 1, num + N + 1); //수열이 오름차순으로 나오게 하기 위해 오름차순 정렬
func(1); //1번째 자리를 선택할 차례
return 0;
}