6009 : 백트래킹 — N-Queen 최적화
•시간제한: 2.000 S
•메모리제한: 256 MB
•제출: 0
•통과: 0
•만든사람: suakii
문제 설명
$N \times N$ 크기의 체스판 위에 $N$개의 퀸을 서로 공격할 수 없도록 배치하는 모든 경우의 수를 구하십시오.
시간 제한 내에 연산을 마치기 위해, 대각선 및 열 체크를 비트마스크(Bitmask) 연산으로 가속화한 최적화된 백트래킹(가지치기) 알고리즘을 사용해야 합니다.
[제약 조건]
• 퀸의 수 $N$: $1 \le N \le 15$ (정수)
• 가지치기(Pruning) 최적화가 필요합니다.
시간 제한 내에 연산을 마치기 위해, 대각선 및 열 체크를 비트마스크(Bitmask) 연산으로 가속화한 최적화된 백트래킹(가지치기) 알고리즘을 사용해야 합니다.
[제약 조건]
• 퀸의 수 $N$: $1 \le N \le 15$ (정수)
• 가지치기(Pruning) 최적화가 필요합니다.
입력 설명
첫째 줄에 체스판의 크기이자 퀸의 개수인 정수 $N$이 주어집니다.
[제약 조건]
• $1 \le N \le 15$
출력 설명
$N$개의 퀸을 서로 공격할 수 없도록 배치하는 모든 경우의 수를 출력합니다.
입력 예시
COPY
복사되었습니다!
복사되었습니다!
8
출력 예시
COPY
복사되었습니다!
복사되었습니다!
92도움
열, 대각선1, 대각선2의 공격 범위를 비트마스크 변수로 관리하여 $O(1)$ 비트 연산으로 배치 가능 여부를 판별합니다.