[백준#C++] N-Queen
문제
https://www.acmicpc.net/problem/9663
접근 과정
- 맨 위부터 하나하나 내려가면서 퀸을 배치하기 때문에 밑을 체크할 필요가 없다.
- 현재 퀸 기준 왼쪽 대각선, 위, 오른쪽 대각선만을 고려
코드
#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
#include <cstring>
using namespace std;
int n;
int ans;
int check[16][16];
int dy[3] = {-1,-1,-1};
int dx[3] = {-1,0,1};
//void input() {}
int check_Q(int y,int x) {
// 밑으로 내려가면서 채우기 때문에 위쪽만 체크
// 왼위 대각, 위, 오른위 대각
for (int i = 0; i < 3; i++) {
int ny = y;
int nx = x;
while (true) {
ny = ny + dy[i];
nx = nx + dx[i];
//경로에 퀸 X
if (nx < 0 || nx >= n || ny < 0 || ny >= n) break;
if (check[ny][nx] == 1) return 0;
}
}
return 1;
}
void go(int y) {
//y가 배열 마지막에 닿을 때
if (y == n) {
ans++;
return;
}
for (int x = 0; x < n; x++) {
if (check_Q(y, x) && check[y][x] == 0) {
check[y][x] = 1;
go(y + 1);
check[y][x] = 0;
}
}
}
int main() {
//freopen("input.txt", "r", stdin);
scanf("%d",&n);
go(0);
printf("%d", ans);
return 0;
}
Author And Source
이 문제에 관하여([백준#C++] N-Queen), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@tunakim/백준C-N-Queen저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)