반응형
https://www.acmicpc.net/problem/9663
문제 해결 알고리즘
대표적인 백트래킹 문제
아래의 링크에 푸는 방법이 있습니다.
https://kimmessi.tistory.com/86?category=871925
소스 코드
#include <bits/stdc++.h>
using namespace std;
int N, cnt;
int col[16];
bool promising(int i){
int k = 1;
bool flag = true;
while(k<i && flag){
if(col[i] == col[k] || abs(col[i] - col[k]) == i-k) flag = false;
k++;
}
return flag;
}
void queens(int i){
if(promising(i)){
if(i == N) cnt++;
else {
for(int j=1;j<=N;j++){
col[i+1] = j;
queens(i+1);
}
}
}
}
int main(){
ios_base::sync_with_stdio(0); cin.tie(0);
cin >> N;
queens(0);
cout << cnt;
}
반응형
'알고리즘 문제 해결 > BOJ' 카테고리의 다른 글
[위상 정렬] BOJ 2056 작업 (0) | 2022.06.19 |
---|---|
[위상 정렬] BOJ 14567 선수과목 (Prerequisite) (0) | 2022.06.18 |
[LIS, 이분 탐색] BOJ 12738 가장 긴 증가하는 부분 수열 3 (C++) (0) | 2022.06.13 |
[LIS, DP] BOJ 11053 가장 긴 증가하는 부분 수열 (C++) (0) | 2022.06.13 |
[LIS, 이분 탐색] BOJ 14003 가장 긴 증가하는 부분 수열 5 (C++) (0) | 2022.06.07 |