🎡 N-Queen
(https://www.acmicpc.net/problem/9663)
시간 제한 메모리 제한 제출 정답 맞힌 사람 정답 비율
10 초 128 MB 55113 27793 18185 49.896%문제
N-Queen 문제는 크기가 N × N인 체스판 위에 퀸 N개를 서로 공격할 수 없게 놓는 문제이다.
N이 주어졌을 때, 퀸을 놓는 방법의 수를 구하는 프로그램을 작성하시오.
입력
첫째 줄에 N이 주어진다. (1 ≤ N < 15)
출력
첫째 줄에 퀸 N개를 서로 공격할 수 없게 놓는 경우의 수를 출력한다.
예제 입력 1
8
예제 출력 1
92
🙄풀이
- 퀸을 체스판 n 번째 행에 둘 수 있는 경우에는 N-Queen 을 만족한 것!
- 퀸을 1번째 행의 i(1~n)번째 열부터 놓으면서 2,3,4 ..., n 번째 행으로 진입 가능 여부를 판단할 것.
- 이때 진입 가능 여부를 판단하는 방법이 중요함.
- 단순히, 퀸이 (x,y) 에 위치할 때 퀸의 공격범위 내에 퀸이 있는지 계속 확인해줘도 되긴 하겠지만 시간이 오래 걸리고 구현하기 번거로울 것으로 예상. (퀸을 한번 놓을때마다 확인절차를 계속 걸쳐야 하므로)
퀸을 (row,col) 에 놓았을 때 확인해야 할 점
- A: 퀸과 같은 열에 새로운 퀸을 둘 수 없음.
-> bool isused_col[]- B: 퀸을 포함하는 우상향 대각선 라인에 새로운 퀸을 둘 수 없음.
-> bool isused_Increasing_Diagonal[]- C: 퀸을 포함하는 좌하향 대각선 라인에 새로운 퀸을 둘 수 없음.
-> bool isused_Decreasing_Diagonal[]
(변수 네이밍이 마음에 안들긴 하지만...)
- 퀸을 (0,0) ~ (0,n) 에 놓으면서 A, B, C 를 확인하며 새로운 퀸을 (1,0)~ (1,n) 에 놓을 수 있는지 확인함.
- 이 과정을 걸쳐 결국 n 행에 퀸을 놓을 수 있다면 count ++
근데, A,B,C indexing 을 어떻게 해야할까?
만약 (x,y) 에 퀸이 위치한다고 가정하자.
-
A: 퀸과 같은 열에 새로운 퀸을 둘 수 없음.
-> bool isused_col[]
조건 같은 경우에는 그냥 isused_col[y] 를 확인해주면 된다. -
B: 퀸을 포함하는 우상향 대각선 라인에 새로운 퀸을 둘 수 없음.
-> bool isused_Increasing_Diagonal[]
위 그림과 같이 0행 0열을 지나가는 우상향 대각선의 index를 0이라고 하고, 이 대각선을 기준으로 한 칸씩 내려오는 대각선의 index 를 1,2,3 ... 이라고 하면 된다.
이렇게 정한 경우에는 퀸이 (x,y) 에 위치한다면 isused_Increasing_Diagonal[x+y] 를 모조리 true 로 해주면 될 것. -
C: 퀸을 포함하는 좌하향 대각선 라인에 새로운 퀸을 둘 수 없음.
-> bool isused_Decreasing_Diagonal[]
이 경우도 똑같지만 살짝 귀찮을 수 있다.
0행 15열을 지나는 대각선의 index 를 0이라고 하고, 한 칸씩 내려오는 대각선의 index 를 1,2,3 ... 이라고 하였다.
이렇게 정한 경우에는 만약 퀸이 (x,y) 에 위치한다면 true 처리해야 하는 index 는 x-y+n-1 로 하면 된다.
( 왜 -1을 해주었냐면, index를 0에서부터 시작하게 하기 위함이다.)
isused_Decreasing_Diagonal[x-y+n-1]
코드
/*
BOJ : https://www.acmicpc.net/problem/9663
backtracking N-Queen
Versatile0010
*/
#include <bits/stdc++.h>
using namespace std;
int n;
int cnt = 0;
bool isused_col[30];
bool isused_Increasing_diagonal[30];
bool isused_Decreasing_diagonal[30];
void func(int cur) // cur 번째 행에 퀸을 배치함
{
if (cur == n)
{
cnt++;
return;
}
for (int i = 0; i < n; i++) // cur 행 i 열을 순회
{
if (isused_col[i] || isused_Increasing_diagonal[cur+i] || isused_Decreasing_diagonal[cur-i+n-1])
continue; // 퀸을 놓을 수 없는 경우
else // 퀸을 놓을 수 있는 경우
{
isused_col[i] = true; // 해당 칸 세로에 true
isused_Increasing_diagonal[cur + i] = true; //해당 칸 우상향 대각선에 true
isused_Decreasing_diagonal[cur - i + n - 1] = true; //해당 칸 좌하향 대각선에 true 처리
func(cur + 1);
isused_col[i] = false;
isused_Increasing_diagonal[cur + i] = false;
isused_Decreasing_diagonal[cur - i + n - 1] = false;
}
}
}
int main()
{
ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
cin >> n;
func(0);
cout << cnt;
return 0;
}GIT : https://github.com/versatile0010/PS/blob/main/Backtracking/BOJ%209663.cpp
